hihocoder-1121 二分图的判定

题目链接：https://cn.vjudge.net/problem/HihoCoder-1121

模板题，思路已经在题干中说明了

也可参照 http://www.cnblogs.com/digitalhermit/p/5119908.html

AC代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int t,n,m;
int color[10010];//记录顶点的颜色（只有两种，1或-1）
vector<int> G[50000];

bool dfs(int v,int c)
{
    color[v]=c;//染色
    int i;
    for(i=0;i<G[v].size();++i)
    {
        if(color[G[v][i]]==c)//如果邻接点与该点同色
            return false;
        if(color[G[v][i]]==0)//如果邻接点未染色
            if(!dfs(G[v][i], -c))//-c表示染成另外一种颜色
                return false;
    }
    return true;//该点的所有邻接点都染色成功了
}

void solve()
{
    int i;
    for(i=0;i<n;++i)//遍历每个顶点
    {
        if(color[i]==0)//如果该顶点未染色
        {
            if(!dfs(i,1))
            {
                printf("Wrong\n");
                return;
            }
        }
    }
    printf("Correct\n");
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(color,0,sizeof(color));
        scanf("%d%d",&n,&m);
        int i;
        for(i=0;i<=n;++i) G[i].clear();//清空vector
        for(i=0;i<m;++i)//建图
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);//无向图所以要反过来连接一次
        }
        solve();
    }
    return 0;
}