二分图判定

给定一个具有n个顶点的图，要给图上每个顶点染色，并且要使相邻的顶点颜色不同，问是否能最多用2种颜色进行染色，题目保证没有重边和自环。

1<=n<=1000 把相邻顶点染成不同颜色的问题叫做着色问题，对图进行染色所需要的最小颜色称为最小着色数，最小着色数为2的图称作二分图。

如果只用2种颜色，那么确定一个顶点的颜色之后，和它相邻的顶点的颜色也就确定了，因此，选择任意一个顶点出发，依次确定相邻顶点的颜色，

就可以判断是否可以被2种颜色染色了。dfs可以简单实现。

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 1010;
int V,E;
vector<int>G[maxn];
int color[maxn];

bool dfs(int v,int c){
    color[v]=c;
    int l=G[v].size();
    for(int i=0;i<l;i++) {
        if(color[G[v][i]]==c)return false;
        if(color[G[v][i]]==0&&!dfs(G[v][i],-c)) return false;
    }
    return true;
}

void solve() {
    for(int i = 0; i < V; i++) {
        if(color[i]==0) {
            if(!dfs(i,1)) {
                printf("No
");
                return;
            }
        }
    }
    printf("Yes
");
}

int main()
{
    //freopen("a.txt","r",stdin);
    scanf("%d%d",&V,&E);
    for(int i=0;i<E;i++) {
        int s,t;
        scanf("%d%d",&s,&t);
        G[s].push_back(t);
        G[t].push_back(s);
    }
　　 memset(color,0,sizeof(color));
    solve();
    return 0;
}