染色法判定二分图（with链式前向星）

---

前言

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。

如下就是一个二分图

基于以上事实，可以得到这样一个结论：

对于二分图中任意的一条边，它的两个邻点必是属于两个不同的集合，否则就不是二分图。
进一步得，判定二分图的方法是看它包不包含这样一个“环”，该环上的边数是奇数。

那么这里所谓的环是什么意思呢？以蓝色、绿色两个颜色作以区分，分别代表两个点所属的集合。

如下图所示，由于这条路径起于蓝点而终于蓝点，构成了封闭性，那么可以把他它想象成如右所示的环，此时路径的长度为4是偶数，所以它构成了一个合法的环，并且从二分图“边的性质”来看也是如此。

依据上述规则再构造如下图，此时它就不是一个合法的环，因为它不满足于“边上两个邻点属于两个不同的集合”这一性质，此时再来数路径上的边数可以看到为5即奇数。

由此得出二分图中“边的性质”和“环的性质”是互为充分必要的关系。

---

染色法判定：

那么依据上述推论若要判断一个图是否为二分图，可以将一个还未归属于任一集合的点先置入一个集合，这个操作可以想象成染色，然后再给邻点染另外一种颜色，再给邻点的邻点染回这个颜色… …，所染的颜色过程交替分布，可以直观地想到，这是一个dfs的过程，遍历这个点所在路径上所有的点。
如果这个操作是“不受阻碍的”，那么这个点所在的路径构成一个合法环，对所有的点重复以上操作，所有操作都是“不受阻碍”的话，就说明图是一个二分图。

这里所谓受阻碍的操作是指，当准备给某个点染色时，判断出它已被染色，并且它染的颜色与其邻点相同，则说明出现了奇数环，整个判图过程终止，返回false。

注意染的颜色有且仅有两个，可以用int型的1和2来区分表示。

---

题目描述

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式

如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围

1≤n,m≤10e5

输入样例：

4 4
1 3
1 4
2 3
2 4
1
2
3
4
5

输出样例：

Yes
1

---

链式前向星

首先，点的个n数较大，如果使用邻接矩阵来存的话内存较大。
而考虑到本题的主要做法是对点做dfs操作，并且为了节省内存，可以使用邻接表结构来存，而这种邻接表在此处有一个很好听的名字——链式前向星。

关于这种数据结构的具体图示和介绍，可以参考如下两个资料：

【AgOHの数据结构】你真的了解链式前向星吗？-哔哩哔哩。

链式前向星详解及其遍历和dfs删边优化。

这里只会用上它的点连接操作：

//数组模拟

void add(int a, int b){         //连接b点和a点，前插法：b指向a
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
1
2
3
4
5
6
7

其中，e[idx]表示的地址为idx的结点编号，ne[idx]表示该点所连接的下一个点的结点地址，h[a]表示结点a的所在路径上的头结点编号（类似于链表）。
那么上述操作还有另一个隐含意义：每次连接点时，总是将b置为a点头结点，即前插法。

---

C++代码

#include 
#include 
#include 
using namespace std;

const int N = 10e5 + 10, M = 2 * 10e5 + 10;

int n, m, idx = 0;
int e[M], ne[M], h[M];      //利用邻接表（链式前向星）存储
int color[N];

void add(int a, int b){         //连接b和a，前插：b指向a
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

bool dfs(int u, int c){     //c的取值：1 || 2，区分两个集合，3 - c即可完成1、2交替映射
    color[u] = c;

    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];       //邻接点：j1 -> j2 -> j3 ->...
        if(!color[j]){       //点j还未被染色
            if(!dfs(j, 3 - c))      return false;
        }
        else if(color[j] == c)      return false;       //染色出现矛盾：c的下一个点还是属于c
    }

    return true;
}

int main(){
    ios :: sync_with_stdio(false);
    memset(h, -1, sizeof(h));
    cin >> n >> m;

    while(m --){
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    //给每个点染色（初色均为1）
    //并dfs每个点所在的环（不一定是环，只是遍历一遍跟该点邻接的所有点），看是否存在染色矛盾
    for(int i = 1;i <= n;i ++){     
        if(!color[i]){
            if(!dfs(i, 1)){
                puts("No");
                return 0;
            }    
        }
    }

    puts("Yes");

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