# 二分图（偶图）及其判定 --- ## 定义 二分图，又称二部图，英文名叫 Bipartite graph。 二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。 换言之，存在一种方案，将节点划分成满足以上性质的两个集合。  --- ## 性质 - 如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。 - 二分图不存在长度为奇数的环 因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。 --- ## 判定 如何判定一个图是不是二分图呢？ 换言之，我们需要知道是否可以将图中的顶点分成两个满足条件的集合。 显然，直接枚举答案集合的话实在是太慢了，我们需要更高效的方法。 考虑上文提到的性质，我们可以使用 [DFS（图论）](./dfs.md) 或者 [BFS](./bfs.md) 来遍历这张图。如果发现了奇环，那么就不是二分图，否则是。 考虑用染色法进行二分图的判定。大致思想为：尝试用黑白（c = 0或1）两种颜色标记图中的结点。当一个节点被标记后，它的所有相邻节点被标记为与它相反的颜色(c ^ 1）。若标记过程中产生冲突，则说明图中存在奇环。 --- ## 示例代码 ```c++ const int N = 505; int m,n; int color[N]; vector<int> node[N]; bool dfs(int v, int c){ color[v] = c; //为当前顶点上色 for(int i = 0; i < node[v].size(); i++){ //遍历所有与之连接的顶点，即相邻顶点 if(color[node[v][i]] == c) //如果相邻的顶点同色，就返回false return false; if(color[node[v][i]] == 0 && !dfs(node[v][i], -c)) //如果相邻顶点未染色，就将其染为相反颜色即-c，并继续dfs return false; //返回false } return true; //直到所有顶点都被染色，且没出现相邻同色顶点，就返回true } void check() { for(int i = 0; i < n; i++) { //遍历所有顶点 if(color[i] == 0){ //如果未染色，就进入深搜 if(!dfs(i, 1)){ printf("NOT BICOLORABLE.\n"); //如果返回false值，就不是二分图 return; //结束搜索 } } } printf("BICOLORABLE.\n"); //未出现相邻同色，就是二分图 } ``` --- ## 典型题目 [NOIPS2010C. 关押罪犯](http://39.99.183.126:8888/p/NOIPS2010C)