染色法判断二分图(dfs + 染色法)

acwing 860染色法判断二分图
**二分图定义:
顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
二分图性质:
1.如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。
2.二分图不存在长度为奇数的环

解法:我们可以利用染色法进行判断,对于一个节点我们可以把它染成颜色1,或者颜色2,0表示当前未染色。
我们利用dfs进行匹配,结论:如果当前出现相邻节点相同颜色说明染色失败,那么当前图不是二分图

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
vector<int>g[maxn];
int n,m;
int st[maxn];
bool dfs(int u, int col){
st[u] = col;
for(int i = 0; i < g[u].size(); i++){
int j = g[u][i];
if(!st[j]){
if(!dfs(j, 3 - col))return 0;
}else if(st[j] == col)return 0;
}
return 1;
}
int main(){
IOS;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int flag = 1;
for(int i = 1; i <= n; i++){
if(!st[i]){
if(!dfs(i, 1)){
flag = 0;
break;
}
}
}
if(flag)cout << "Yes" <<'n';
else cout << "No" << 'n';
}

最后

以上就是时尚香菇为你收集整理的染色法判断二分图(dfs + 染色法)的全部内容，希望文章能够帮你解决染色法判断二分图(dfs + 染色法)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。