題目描述
圓桌騎士是一個非常吸引人的職業。因此，在最近幾年里，亞瑟王史無前例的擴招圓桌騎士，并不令人驚訝。現在這里有許多圓桌騎士，每個圓桌騎士都收到一份珍貴的邀請函，被邀請去英靈殿圓桌。這些騎士將要環繞著坐在一個圓桌旁，但通常只有一小部分騎士會來，因為剩下的騎士正忙著在全國各地為人民服務。
不幸的是，這些圓桌騎士的酒量不行，很容易喝高。當他們喝高時，一些不幸的便當事件將會發生。因此，亞瑟王請來了長門大神，來確保在未來不會有類似的事情發生。在仔細分析了這個問題后，長門大神意識到要想避免騎士之間相互斗毆，當且僅當他們在圓桌旁所坐的位置，符合以下條件：
1. 某些騎士之間有仇，避免相互之間有仇的騎士挨在一塊。
2. 當場上有偶數個騎士時，若通過投票解決問題的話，正方與反方的票數可能相同，這會令騎士們非常不爽。因此，只能有奇數個騎士坐在圓桌旁。
長門大神會盡量的滿足以上兩個條件，否則她會代替亞瑟王宣布散會（若只有一個騎士在場的話，也會宣布散會，因為一個騎士不管怎么坐，都不可能環繞一個圓桌）。這將意味著無論如何安排，一些騎士都無法到場，無法坐在圓桌旁邊（其中一種情況即為當這個騎士對所有騎士都有仇時，當然還可能是其他情況）。若一個圓桌騎士永遠無法到場，則這個騎士就失去了“圓桌”的意義，他將會被開除。這些騎士將會被降級，降到諸如“愛的戰士”“蘑菇騎士”“人魚騎士”之類的職階。
為了幫助長門大神，你必須寫一個程序來計算會有多少圓桌騎士會被開除。
輸入
輸入有多組，每組第一行兩個整數，N和M，N為騎士的數量。
接下來M行每行兩個整數i,j，表示i與j之間有仇恨。
輸入數據保證不會有重邊和自環。
0 0 代表輸入結束
?
輸出
一個整數，為所求的答案。
樣例輸入
5 51 21 32 32 43 50 0
樣例輸出
2
提示
1 ≤ n ≤ 1000 and 1 ≤ m ≤ 1000000
?
步驟：
1.先將沒有仇恨的騎士兩兩建邊。
2.求一遍雙連通分量。
3.在同一連通分量里面找奇環，若該連通分量存在奇環，則該連通分量的任意兩點都可以形成奇環。（下面有證明）
?
步驟三的證明：
1.首先明確：若存在奇環，則奇環上任意點必存在兩條路徑可以到達，而且長度必為一奇一偶。
2.所以如果再添加一個點或幾個的話，他們必與此環有聯通，且存在兩條路徑。
3.若單看這新添加的這幾個點或這一個點，他們之間一定存在一條路徑把他們連通，若該路徑為奇數，則可以和環上的偶數路徑搭配，構成奇環。反之，若為偶數，則可以和環上的奇數路徑搭配，構成奇環。所以無論如何都可以搭配成奇環。
?
下面是代碼：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<vector> 7 using namespace std; 8 9 int gi() 10 { 11 int str=0; 12 char ch=getchar(); 13 while(ch>'9'||ch<'0')ch=getchar(); 14 while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar(); 15 return str; 16 } 17 const int N=1001; 18 int n,m; 19 bool d[N][N]; 20 int num=0; 21 struct Lin 22 { 23 int next,to; 24 } a[N*N*2]; 25 int head[N]; 26 int ans=0; 27 int color[N]; 28 bool c[N]; 29 30 void init(int x,int y) 31 { 32 a[++num].next=head[x]; 33 a[num].to=y; 34 head[x]=num; 35 } 36 vector<int>q[N]; 37 int dfn[N],low[N],st[N],top=0,NUM=0,flg[N],bel[N],sum=0; 38 39 40 void Clear() 41 { 42 memset(d,0,sizeof(d)); 43 for(int i=1; i<=N-1; i++) 44 { 45 dfn[i]=low[i]=flg[i]=bel[i]=color[i]=head[i]=st[i]=c[i]=0; 46 q[i].clear(); 47 } 48 num=NUM=top=ans=sum=0; 49 } 50 51 void dfs(int x,int last) 52 { 53 int u,v; 54 dfn[x]=low[x]=++NUM; 55 flg[x]=1; 56 st[++top]=x; 57 for(int i=head[x]; i; i=a[i].next) 58 { 59 u=a[i].to; 60 if(u==last)continue; 61 if(!dfn[u]) 62 { 63 dfs(u,x); 64 low[x]=min(low[x],low[u]); 65 if(low[u]>=dfn[x]) 66 { 67 sum++; 68 while(top) 69 { 70 v=st[top--]; 71 flg[v]=false; 72 bel[v]=sum; 73 q[sum].push_back(v); 74 if(v==u)break; 75 } 76 q[sum].push_back(x); 77 } 78 } 79 else if(flg[u])low[x]=min(dfn[u],low[x]); 80 } 81 } 82 83 bool Make(int x) 84 { 85 int u; 86 for(int i=head[x]; i; i=a[i].next) 87 { 88 u=a[i].to; 89 if(bel[u]!=bel[x])continue; 90 if(color[u]==color[x])return false; 91 if(!color[u]) 92 { 93 color[u]=3-color[x]; 94 if(!Make(u))return false; 95 } 96 } 97 return true; 98 } 99 100 void work() 101 { 102 int x,y; 103 for(int i=1; i<=m; i++) 104 { 105 x=gi(); 106 y=gi(); 107 d[x][y]=d[y][x]=1; 108 } 109 for(int i=1; i<=n; i++) 110 for(int j=i+1; j<=n; j++) 111 if(!d[i][j])init(i,j),init(j,i); 112 for(int i=1; i<=n; i++)if(!dfn[i])dfs(i,i); 113 114 bool ff=1; 115 int size; 116 ans=0; 117 for(int i=1; i<=sum; i++) 118 { 119 if(q[i].size()<=2)continue; 120 memset(color,0,sizeof(color)); 121 color[q[i][0]]=1; 122 size=q[i].size(); 123 for(int j=0;j<size;j++)bel[q[i][j]]=i; 124 ff=Make(q[i][0]); 125 if(!ff)for(int j=0;j<size;j++)c[q[i][j]]=1; 126 } 127 for(int i=1;i<=n;i++)if(!c[i])ans++; 128 printf("%d\n",ans); 129 } 130 131 int main() 132 { 133 while(1) 134 { 135 n=gi(); 136 m=gi(); 137 if(!n && !m)break; 138 work(); 139 Clear(); 140 } 141 return 0; 142 }
?
)
)