二分图染色：二步侠PIPI

比眉伴天荒 2023-10-06 20:02 39阅读 0赞

## 二分图染色：二步侠PIPI ##

#### 文章目录 ####

*  二分图染色：二步侠PIPI
 *   *   *  二分图
         *  问题：
         *  思路：
         *  代码：

#### 二分图 ####

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

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

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_17_color_FFFFFF_t_70_g_se_x_16]

#### 思路： ####

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

而偶数环的情况就不同了，由于环中元素为偶数，在一次走两步的情况下，跳过的点怎么都走不到。偶数环如下图所示：  
![在这里插入图片描述][232dc869615c4772ad70fbeb3868a7fe.png]  
  因此，若连通图含奇数环，我们能遍历所有的点，若连通图含偶数环或不含环，我们无法遍历所有的点，此时我们还需增加一条边以形成奇数环。  
  自此该题转化为了求图中的连通分量的数量+判断连通分量中是否含奇数环的问题。如何求图中的连通分量的数量？我们可以使用dfs+标记数组来完成，我们依次遍历每个点，若该点未被标记，则调用dfs函数，将其属于的连通分量中的点全部标记，并使连通分量数加1。  
  如何判断某个连通分量中是否含有奇数环？此时二分图就要登场了，因为一个连通分量是二分图，则该连通分量肯定不存在奇数环。在含奇数环的情况下，染色过程是无法成功的，看下图：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_15_color_FFFFFF_t_70_g_se_x_16]  
  在含奇数环的情况下，一定会发生染色冲突，即不是二分图。若所有连通分量都不含奇数环，即所有连通分量都为二分图，则我们还需增加一条边以形成奇数环。如何判断连通分量是否为二分图？直接模拟染色过程即可，利用`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;
                }
            }
        }
    
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0f1e34958ef849eb9387ae15f8b3b1b2.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/b3fb9558803b49e390b8da5609560552.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_17,color_FFFFFF,t_70,g_se,x_16
[bd00dcf238094a3092c8f2d55dd63b07.png]: https://img-blog.csdnimg.cn/bd00dcf238094a3092c8f2d55dd63b07.png
[232dc869615c4772ad70fbeb3868a7fe.png]: https://img-blog.csdnimg.cn/232dc869615c4772ad70fbeb3868a7fe.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_15_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/9132327592134c9b841abc2515b0f48e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_15,color_FFFFFF,t_70,g_se,x_16
[pipioj-1414]: http://pipioj.online/problem.php?id=1414