hihocoder-1121 二分图的判定

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

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

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

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

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

int t,n,m;
int color[10010];
vector<int> G[50000];

bool (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("Wrongn");
                return;
            }
        }
    }
    printf("Correctn");
}

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;
}