題意：
有N個騎士，給出某些騎士之間的仇恨關系，騎士們開會時會圍坐在一個圓桌旁。一次會議能夠順利舉行，要滿足兩個條件：
1：任意相互憎恨的兩個騎士不能相鄰
2：開會人數為大於2的奇數
若某個騎士任何會議都不能參加，那麼就必須將他踢出，給出騎士之間的仇恨關系，問最少需要踢出多少個騎士？
思路：
題目要求踢出的人最少，那麼其實應該都能盡量坐下來，又不能與仇恨的騎士相鄰。而題目給出的是騎士之間的仇恨關系，因此我們首先建立補圖，先將給出的仇恨關系以騎士為頂點建立邊，然後撤銷這些邊，將其余可以連的邊都連上便是原圖的補圖。騎士要能圍坐在一個圓桌，就是圖中頂點能在一個圈中，即在一個雙連通分量裡，而題目要求的要開會的人數是大於2的奇數，那麼此題就是求最多有多少個騎士在奇圈中。
要求最多有多少騎士在奇圈中，關於奇圈我們要承認這兩個定理：
1：若雙連通分量中有一個奇圈，則該雙連通分量中的所有點都在某個奇圈中
2：若一個雙連通分量有奇圈，那麼該雙連通分量必定不是二分圖，他們是充分必要條件。判斷是否是二分圖可以用交叉染色法，即深度優先搜索染色，如果搜到一個節點的子節點已經染色並且與自己相同，說明不是二分圖，那麼雙連通分量中有奇圈。
這裡注意雙連通分量裡的頂點個數是否是奇數與該雙連通分量是否是奇圈無關。
我們可以用tarjan求出每個雙連通分量，在其頂點大於2的前提下,對每次求出的雙連通分量，根據交叉染色法判斷是否有奇圈，如果有，那麼這個雙連通分量中的點都不用刪除（標記一下即可）。
最後，沒被標記的肯定不是任何一個奇圈中的頂點。
#include#include #include #include #include using namespace std; const int maxn = 1010; const int maxm = 1000100; int map[maxn][maxn]; int n,m; int dfn[maxn],low[maxn],instack[maxn],dep; int scc,tmp[maxn],block[maxn]; int color[maxn];//給某個雙連通深度優先搜索染色 int expell[maxn];//標記頂點是否在某個奇圈中 int cnt; stack st; vector edge[maxn];//補圖 void init() { for(int i = 1; i <= n; i++) edge[i].clear(); while(!st.empty()) st.pop(); memset(map,0,sizeof(map)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(instack,0,sizeof(instack)); memset(block,0,sizeof(block)); memset(expell,0,sizeof(expell)); dep = 0; cnt = 0; scc = 0; } //判斷奇圈 bool odd_cycle(int u,int col) { color[u] = col; for(int i = 0; i < (int)edge[u].size(); i++) { int v = edge[u][i]; if(block[v] == scc) { if(color[v] && color[v] == color[u]) return true; if(!color[v] && odd_cycle(v,-col)) return true; } } return false; } void tarjan(int u, int fa) { dfn[u] = low[u] = ++dep; instack[u] = 1; st.push(u); for(int i = 0; i < (int)edge[u].size(); i++) { int v = edge[u][i]; if(v == fa) continue; if(!dfn[v]) { tarjan(v,u); low[u] = min(low[u],low[v]); if(low[v] >= dfn[u]) { scc++; int t; do { t = st.top(); st.pop(); instack[t] = 0; tmp[++cnt] = t; block[t] = scc; }while(t != v);//注意不要讓u出棧，因為它可能屬於多個雙連通分量 tmp[++cnt] = u;//u進臨時數組 memset(color,0,sizeof(color)); if(cnt >= 3 && odd_cycle(u,1))//若該雙連通分量包含頂點個數大於2並且是奇圈時 { while(cnt != 0) expell[ tmp[cnt--] ] = 1;//在奇圈內的點全部標記為1 } else cnt = 0;//別忘了將cnt置零 } } else if(instack[v]) low[u] = min(low[u],dfn[v]); } } int main() { int u,v; while(~scanf(%d %d,&n,&m)) { if(n == 0 && m == 0) break; init(); for(int i = 0; i < m; i++) { scanf(%d %d,&u,&v); map[u][v] = map[v][u] = 1; } //求補圖 for(int i = 1; i <= n-1; i++) { for(int j = i+1; j <= n; j++) { if(!map[i][j]) { edge[i].push_back(j); edge[j].push_back(i); } } } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i,-1); int res = 0; for(int i = 1; i <= n; i++) if(expell[i] == 0) res++; printf(%d ,res); } return 0; }
