題意：
有N個(gè)騎士，給出某些騎士之間的仇恨關(guān)系，騎士們開會(huì)時(shí)會(huì)圍坐在一個(gè)圓桌旁。一次會(huì)議能夠順利舉行，要滿足兩個(gè)條件：
1：任意相互憎恨的兩個(gè)騎士不能相鄰
2：開會(huì)人數(shù)為大于2的奇數(shù)
若某個(gè)騎士任何會(huì)議都不能參加，那么就必須將他踢出，給出騎士之間的仇恨關(guān)系，問最少需要踢出多少個(gè)騎士？
思路：
題目要求踢出的人最少，那么其實(shí)應(yīng)該都能盡量坐下來，又不能與仇恨的騎士相鄰。而題目給出的是騎士之間的仇恨關(guān)系，因此我們首先建立補(bǔ)圖，先將給出的仇恨關(guān)系以騎士為頂點(diǎn)建立邊，然后撤銷這些邊，將其余可以連的邊都連上便是原圖的補(bǔ)圖。騎士要能圍坐在一個(gè)圓桌，就是圖中頂點(diǎn)能在一個(gè)圈中， 即在一個(gè)雙連通分量里，而題目要求的要開會(huì)的人數(shù)是大于2的奇數(shù) ，那么此題就是求最多有多少個(gè)騎士在奇圈中
sat答案 要求最多有多少騎士在奇圈中，關(guān)于奇圈我們要承認(rèn)這兩個(gè)定理：
1：若雙連通分量中有一個(gè)奇圈，則該雙連通分量中的所有點(diǎn)都在某個(gè)奇圈中
2：若一個(gè)雙連通分量有奇圈，那么該雙連通分量必定不是二分圖，他們是充分必要條件。判斷是否是二分圖可以用交叉染色法，即深度優(yōu)先搜索染色，如果搜到一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)已經(jīng)染色并且與自己相同，說明不是二分圖，那么雙連通分量中有奇圈
托福答案 這里注意雙連通分量里的頂點(diǎn)個(gè)數(shù)是否是奇數(shù)與該雙連通分量是否是奇圈無(wú)關(guān)。
我們可以用tarjan求出每個(gè)雙連通分量，在其頂點(diǎn)大于2的前提下,對(duì)每次求出的雙連通分量，根據(jù)交叉染色法判斷是否有奇圈，如果有，那么這個(gè)雙連通分量中的點(diǎn)都不用刪除（標(biāo)記一下即可）。
最后，沒被標(biāo)記的肯定不是任何一個(gè)奇圈中的頂點(diǎn)。
#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];//給某個(gè)雙連通深度優(yōu)先搜索染色
int expell[maxn];//標(biāo)記頂點(diǎn)是否在某個(gè)奇圈中
int cnt;
stack st;
vector edge[maxn];//補(bǔ)圖
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出棧，因?yàn)樗赡軐儆诙鄠€(gè)雙連通分量
tmp[++cnt] = u;//u進(jìn)臨時(shí)數(shù)組
memset(color,0,sizeof(color));
if(cnt >= 3 && odd_cycle(u,1))//若該雙連通分量包含頂點(diǎn)個(gè)數(shù)大于2并且是奇圈時(shí)
{
while(cnt != 0)
expell[ tmp[cnt--] ] = 1;//在奇圈內(nèi)的點(diǎn)全部標(biāo)記為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;
}
//求補(bǔ)圖
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;
}