被震驚到了！沒想到圖上的知識居然那麼玄妙。
歸納出兩點：
1.對于一個連通分量内，若二分圖染色後為二分圖，則圖内全為偶環，無奇環。
2.對于一個連通分量内，若二分圖染色後不為二分圖，則圖内全為奇環，無偶環。
證明我還是畫一畫圖吧。
對于結論1。
先來個二分圖
然後選擇其中的一個偶環，
我們發現根據二分圖的性質，從左道右就必定能夠從右到左，那麼這就不是個奇環了。
對于結論2。
我們發現在一個連通分量中，若能找到一個奇環，對于任意一個點連接配接圖上任意兩個點都一定能夠都到包含着個點的一個奇環、一個偶環，易證。
是以說哈哈啦。
code實作也是很簡單的。
一個二分圖染色，一個Tarjan。
//随便貼一份代碼吧。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#define clr(x) memset((x),0,sizeof(x))
using namespace std;
const int N=;
const int M=;
int n,m,i,j,k,l;
int head[N],next[M],list[M],tot,caset;
int dfn[N],low[N],sta[N],sta_tot,cnt__index,bfn[N],bfn_tot,col[N];
int aa[N][N],ans[N];
void add(int a,int b){
tot++;
list[tot]=b;
next[tot]=head[a];
head[a]=tot;
}
bool dfs(int x,int c){
col[x]=c;
for(int i=head[x];i;i=next[i])
if(bfn[list[i]]==bfn_tot){
if(col[list[i]]==c)return false;
else if(col[list[i]]!=(c^)&&dfs(list[i],c^)==false)return false;
}
return true;
}
void colour(int x){
ans[x]=;bfn[x]=-;
for(int i=head[x];i;i=next[i])
if(bfn[list[i]]==bfn_tot)colour(list[i]);
return;
}
int tarjan(int x,int fa){
int i,j,k;
dfn[x]=low[x]=++cnt__index;
sta[++sta_tot]=x;
for(int i=head[x];i;i=next[i])
if(i!=fa){
if(!dfn[list[i]]){
low[x]=min(low[x],tarjan(list[i],i^));
if(low[list[i]]>=dfn[x]){
bfn_tot++;
while(sta[sta_tot+]!=list[i])
bfn[sta[sta_tot--]]=bfn_tot;
bfn[sta[sta_tot]]=bfn_tot;
bfn[x]=bfn_tot;
if(!dfs(x,x<<))colour(x);
}
}
else low[x]=min(low[x],dfn[list[i]]);
}
return low[x];
}
int main(){
while(scanf("%d%d",&n,&m),n||m){
tot=;cnt__index=sta_tot=bfn_tot=;
clr(ans),clr(col),clr(head),clr(bfn),clr(dfn);
caset++;
for(i=;i<=m;i++){
scanf("%d%d",&j,&k);
aa[j][k]=caset;
aa[k][j]=caset;
}
for(i=;i<=n;i++)
for(j=i+;j<=n;j++)
if(aa[i][j]!=caset)
{add(i,j);add(j,i);}
for(i=;i<=n;i++)
if(!dfn[i])tarjan(i,);
k=;
for(i=;i<=n;i++)
if(!ans[i]||!head[i])k++;
printf("%d\n",k);
}
return ;
}