AcWing 860.染色法判断二分图

本文主要是介绍AcWing 860.染色法判断二分图，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：https://www.acwing.com/problem/content/862/

放AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5+10, M = 2e5+10;//因为是无向图所以边的数量*2
 4 int e[M], ne[M], h[N], cnt;
 5 int color[N];
 6 
 7 void add(int u, int v)
 8 {//添加边
 9     e[cnt] = v;
10     ne[cnt] = h[u];
11     h[u] = cnt++;
12 }
13 
14 bool dfs(int u, int c)
15 {//返回flase即有矛盾发生
16     color[u] = c;
17     for(int i=h[u]; i!=-1; i=ne[i])
18     {
19         int j = e[i];//定义临点
20         if(!color[j] && !dfs(j, 3-c)) return false;//如果临点未被染色 且 临点矛盾
21         else if(color[j] == c) return false;//如果临点与此点颜色相同
22     }
23     return true;//如果不矛盾则返回true
24 }
25 
26 int main()
27 {
28     int n, m;
29     cin >> n >> m;
30     memset(h, -1, sizeof h);//初始化
31     while(m--)
32     {
33         int u, v;
34         cin >> u >> v;
35         add(u, v), add(v, u);//因为无向图
36     }
37 
38     //染色
39     bool flag = true;
40     for(int i=1; i<=n; i++)
41         if(!color[i] && !dfs(i, 1))//如果存在点没有被染过颜色，或者出现矛盾
42         {//则证明不是二分图
43             flag = false;
44             break;
45         }
46 
47     if(flag) cout << "Yes" ;
48     else cout << "No";
49     return 0;
50 }

这篇关于AcWing 860.染色法判断二分图的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！