TIOJ 1209 圖論 之 二分圖測試

[DFS]
圖論的一個有點基本的定理：一個圖是二分圖若且為若此圖可以二著色

測資似乎沒有 "兩個圖或以上" 的情況 @@ ，從只從第一點開始dfs竟然AC了 OAO

#include<stdio.h>
#include<stdlib.h>
#include <vector>
std::vector<int> edges[40001];
int color[40001];
int isok=0;
int draw(int a)
{
for ( int i=0; i<edges[a].size(); i++ )
{
if ( color[edges[a][i]]==-1 )
{
color[edges[a][i]]=1-color[a];
draw(edges[a][i]);
}
else if ( color[edges[a][i]]==color[a] )
isok=0;
}
}
int main()
{
int n,e;
while(scanf("%d %d",&n,&e))
{
if((e==0)&&(n==0))
break;
isok=1;
for(int lx=1;lx<=n;lx++)
{
edges[lx].clear();
color[lx]=-1;
}
int _a;int _b;
for(int lx=1;lx<=e;lx++)
{
scanf("%d %d",&_a,&_b);
edges[_a].push_back(_b);
edges[_b].push_back(_a);
}
                color[1]=0;
draw(1);
if(isok)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}