前置知识
二分图,又称二部图,英文名叫 Bipartite graph。
二分图是什么?节点由两个集合组成,且两个集合内部没有边的图。
换言之,存在一种方案,将节点划分成满足以上性质的两个集合。
二分图的重要性质:如果两个集合中的点分别染成黑色和白色,那么二分图的每条边都一定是连接一个黑色点和白色点。
二分图判定定理:一张无向图是二分图当且仅当图中不存在奇环(长度为奇数的环)。
证明:可以自己找个奇环验证一下。
例题:染色法判定二分图
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行,每行包含两个整数 u 和 v,表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图,则输出 Yes,否则输出 No。
数据范围
1≤n,m≤10^5
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes
染色法可以用DFS或者BFS实现。它可以处理重边和自环。
注意:二分图不一定是连通图。所以需要把每个点都搜一遍。
处理所有边和所有点,时间复杂度:O(n+m)。
算法1
DFS
时间复杂度:O(n+m)
参考文献:算法基础课
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
const int N = 1e5+5,M = 2e5+5;
int n,m;
int color[N];
int h[N], e[M], ne[M], idx;
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
bool dfs(int u,int c){// 把u所在连通块染色,判断是否矛盾
color[u] = c;
for (int i = h[u]; ~i;i = ne[i]){
int j = e[i];
if (!color[j]){
// 3-1=2,3-2=1 把相邻点分别染成1和2
if (!dfs(j,3 - c)) return false;// 若j未染色,递归将j相邻节点染色,并判断是否矛盾
}
else if (color[j] == c) return false;// 若j染色,且颜色与u相同,说明矛盾
}
return true;
}
int main(){
IOS;
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ){
int u,v;
cin >> u >> v;
add(u,v),add(v,u);// 无向图存两条边
}
bool flag = true;// 染色成功的标志
for (int i = 1;i <= n;i ++){// 把图中每个点都搜索一遍
if (!color[i]){// 没有染色的才需要染色,搜索
if (!dfs(i,1)){// 把i所在连通块染色,判断是否矛盾
flag = false;// 染色失败,退出
break;
}
}
}
if (flag) cout << "Yes\n";
else cout << "No\n";
return 0;
}
算法2
BFS
时间复杂度:O(n+m)
C++ 代码
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
const int N = 1e5+5,M = 2e5+5;
int n,m;
int color[N];
int h[N], e[M], ne[M], idx;
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
bool bfs(int u,int c){
queue<int> q;
color[u] = c;
q.push(u);
while (q.size()){
int t = q.front();
q.pop();
for (int i = h[t]; ~i;i = ne[i]){
int j = e[i];
if (!color[j]){
color[j] = 3 - color[t];// 注意:不要写成color[u],是和相邻点比较,不是和根比较
q.push(j);
}
else if (color[j] == color[t]) return false;
}
}
return true;
}
int main(){
IOS;
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ){
int u,v;
cin >> u >> v;
if (u != v) add(u,v),add(v,u);
}
bool flag = true;
for (int i = 1;i <= n;i ++){
if (!color[i]){
if (!bfs(i,1)){
flag = false;
break;
}
}
}
if (flag) cout << "Yes\n";
else cout << "No\n";
return 0;
}