二分图染色：二步侠PIPI

文章目录

二分图染色：二步侠PIPI

二分图

二分图/二部图的定义：设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(u,v)所关联的两个顶点u和v分别属于这两个不同的顶点集(u in A,v in B)，则称图G为一个二分图/二部图。简而言之，有两顶点集且图中每条边的两个顶点分别位于两顶点集中，每个顶点集中没有边直接相连，这样的图为二分图。
通过以上定义，我们可以总结出二分图的判定有以下两点：
1、图为连通图。
2、可以分为两个不同的点集。
也就是说，如果可以把每个节点染成黑色或白色之一，使得同色的点没有边直接相连，我们就可以判断该图为二分图。反之，若不可以做到，该图就不为二分图。

即我们从一个点出发，初始时将它染为黑色，遍历整个图，将下一个点染为与当前遍历点不同的颜色，如白色，若我们能遍历完整个图完成染色，则该图为二分图，否则该图不是二分图

问题：

思路：

首先，若要能遍历完图中所有的点，该图一定要是连通图，因此我们需要将图中不同的连通分量连起来，若图中有n个连通分量，我们需要增加n-1条边将它们连通
对于连通图，在每次走两步的情况下我们能遍历所有的点吗？对于一次走两步的问题，一般都与环有联系。我们考虑环的情况，若连通图无环，那么一次走两步，走两步跳过的那些点怎么都走不到。若连通图有环，我们还需进一步讨论环为奇数环还是偶数环（奇数环指环中的元素数为奇数，偶数环指环中的元素数为偶数），对于奇数环的情况，我们能遍历所有的点，因为奇数环可以调整脚步，由于环中元素为奇数，在一次走两步的情况下，我们正好能遍历环中所有元素。奇数环如下图所示：

而偶数环的情况就不同了，由于环中元素为偶数，在一次走两步的情况下，跳过的点怎么都走不到。偶数环如下图所示：

因此，若连通图含奇数环，我们能遍历所有的点，若连通图含偶数环或不含环，我们无法遍历所有的点，此时我们还需增加一条边以形成奇数环。
自此该题转化为了求图中的连通分量的数量+判断连通分量中是否含奇数环的问题。如何求图中的连通分量的数量？我们可以使用dfs+标记数组来完成，我们依次遍历每个点，若该点未被标记，则调用dfs函数，将其属于的连通分量中的点全部标记，并使连通分量数加1。
如何判断某个连通分量中是否含有奇数环？此时二分图就要登场了，因为一个连通分量是二分图，则该连通分量肯定不存在奇数环。在含奇数环的情况下，染色过程是无法成功的，看下图：

在含奇数环的情况下，一定会发生染色冲突，即不是二分图。若所有连通分量都不含奇数环，即所有连通分量都为二分图，则我们还需增加一条边以形成奇数环。如何判断连通分量是否为二分图？直接模拟染色过程即可，利用color[]数组表示每个结点的颜色，在dfs过程中，将当前遍历结点相邻的未染色结点染上与当前节点不同的颜色（color[next] = (-1) * color[now]），若相邻结点已被染色，则判断是否发生染色冲突（color[next] == color[now]），若发生冲突，则不是二分图。颜色数组也能充当标记数组的作用，没被染色的结点即为未访问节点。

代码：

C++：

#include <bits/stdc++.h>
using namespace std;
vector<int> mp[100002];
int color[100002];
bool notTwoMap = false;
void dfs(int node) {
	    int i, next;
        for (i = 0;i < mp[node].size();i++) {
            next = mp[node][i];
            if (color[next] == 0) {
                color[next] = (-1) * color[node];
                dfs(next);
            } else if (color[next] == color[node]) {
                notTwoMap = true;
            }
        }
}
int main() {
	int n,m,i,u,v,ans=0;
    scanf("%d%d",&n,&m);
    for (i = 0;i < m;i++) {
        scanf("%d%d",&u,&v);
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    for (i = 1;i <= n;i++) {
            if (color[i] == 0) {
                color[i] = 1;
                ans++;
                dfs(i);
            }
    }
    ans--;
    if (!notTwoMap) {
        ans++;
    }
    printf("%d\n",ans);
	return 0;
}

Java：
Java代码提交到oj会报RuntimeError，不知具体原因，若有大佬发现错误原因，请在评论中指正，不胜感激。oj链接如下：pipioj-1414

import java.util.*;

public class Main {
	// 颜色数组
    static int[] color = new int[100002];
    // 邻接表
    static List<Integer>[] adj = new List[100002];
    // 判断所有连通分量是否都是二分图,
    // notTwoMap = true表示有连通分量不是二分图
    static boolean notTwoMap = false;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n, m, u, v, i, ans = 0;
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (i = 0;i <= n;i++) {
            adj[i] = new ArrayList<>();
        }
        for (i = 0;i < m;i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }
        // 求连通分量数以及判断所有连通分量是否都是二分图
        for (i = 1;i <= n;i++) {
            if (color[i] == 0) {
                color[i] = 1;
                ans++;
                dfs(i);
            }
        }
        // 补充边，使整个图为连通图，补充边数为连通分量数-1，这里为-1操作
        ans--;
        // 若连通分量全为二分图，则还需增加一条边以形成奇数环
        if (!notTwoMap) {
            ans++;
        }
        System.out.println(ans);

    }

    static void dfs(int node) {
        int i, next;
        for (i = 0;i < adj[node].size();i++) {
            next = adj[node].get(i);
            // 相邻点未被访问
            if (color[next] == 0) {
                color[next] = (-1) * color[node];
                dfs(next);
            } else if (color[next] == color[node]) {
            	// 发生染色冲突，不为二分图
                notTwoMap = true;
            }
        }
    }

}