题意简述

给定多个连通无向图，判断这些图是不是二分图。

Step 1 建图

$2\le n\le 199$，邻接矩阵和邻接表大家都随意，根据自己的习惯来。我这里用的是 vector 实现邻接表。

另外，因为结点的编号是从 $0\sim n-1$，我不太习惯，于是在建图的时候就擅自每个结点的编号都 $+1$，把编号变成了 $1\sim n$。

1
2
3
4
5
for(int i=1;i<=m;i++){
    scanf("%d %d",&u,&v);
    map1[u+1].push_back(v+1);
    map1[v+1].push_back(u+1);
}

Step 2 发出开始染色的指令

（没错我在凑字数）

Tips：以下内容都把结点编号当成 $1\sim n$。

因为是连通图，所以我们从 $1$ 结点开始染色。

我们定义一个 $a$ 数组，$a_i$ 代表 $i$ 结点的颜色：$0$ 代表还没有染色，$1$ 和 $2$ 代表两种不同的颜色。$1$ 号结点随便染一个颜色。

函数里可以传一个参数（遍历到的结点编号），也可以传两个参数（遍历到的结点编号和这个结点染的颜色）。我传的是两个参数。

主函数的执行异常简单，用三目运算符可以压缩为一行：

1
printf("%s",dfs(1,1)?"BICOLORABLE\n":"NOT BICOLORABLE\n");

Step 3 染色

染色我们采用 dfs 来执行。其实 bfs 也可以实现，但是显然 dfs 码量比 bfs 少亿丶丶，而且 bfs 要开结构体队列，内存更大，所以我们就使用 dfs 了。

dfs 的思路和遍历图差不多。因为只有两个颜色，所以定了 $1$ 结点的颜色后，染色的方案是唯一的。我们先找到给定点的所有直接后继，然后一个一个看：

  • 如果它的某个直接后继与它要求染的颜色相同，这个图就不是二分图，直接 return false 即可。

  • 如果它的某个直接后继和他要求染的颜色不同，那么直！接！跳！过！

  • 如果它的某个直接后继没有染色，那么就给这个直接后继染上与它不同的颜色，接着继续遍历这个刚被染色的直接后继的直接后继。如果此直接后继后面染色不成功，说明这个图不是二分图（因为方案唯一！），直接 return false。

如果遍历完了，就 return true。

1
2
3
4
5
6
7
8
9
10
int f(int x){return (x==1)?2:1;} //取相反颜色
bool dfs(int x,int color){
    a[x]=color;
    for(int i=0;i<map1[x].size();i++){
        if(a[map1[x][i]]==color) return 0;
        if(a[map1[x][i]]==f(color)) continue;
        if(!dfs(map1[x][i],f(color))) return 0;
    }
    return 1;
}

Step 4 其它

一定要初始化！一定要初始化！一定要初始化！

要初始化的是图和记录染色的数组。

1
2
memset(map1,0,sizeof(map1)); //vector可以直接这么初始化
memset(a,0,sizeof(a));

另外这是邻接表的检查代码：

1
2
3
4
5
for(int i=1;i<=n;i++){
    printf("%d: ",i);
    for(int j=0;j<map1[i].size();j++) printf("%d ",map1[i][j]);
    printf("\n");
}

Code

最后双手献上 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
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> map1[205];
int n,m,u,v,a[205];
int f(int x){return (x==1)?2:1;}
bool dfs(int x,int color){
    a[x]=color;
    for(int i=0;i<map1[x].size();i++){
        if(a[map1[x][i]]==color) return 0;
        if(a[map1[x][i]]==f(color)) continue;
        if(!dfs(map1[x][i],f(color))) return 0;
    }
    return 1;
}
int main(){
    while(10000000000000000000ull>9999999999999999999ull){ //没问题是吧
        memset(map1,0,sizeof(map1));
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        if(!n) return 0;
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            scanf("%d %d",&u,&v);
            map1[u+1].push_back(v+1);
            map1[v+1].push_back(u+1);
        }
        /*for(int i=1;i<=n;i++){
            printf("%d: ",i);
            for(int j=0;j<map1[i].size();j++) printf("%d ",map1[i][j]);
            printf("\n");
        }*/
        printf("%s",dfs(1,1)?"BICOLORABLE.\n":"NOT BICOLORABLE.\n");
    }
    return 0;
}

提交记录：Link（没错我 UVA 登上了）