题目描述
给定一个n个点m条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
样例
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes
算法1
(递归) $O(n + m)$
1.先建图
2.对每个顶点进行遍历。
3.再确定哪个顶点的情况下,找到该顶点所连的边,就可以找到下一个顶点,进行染色。染色的时候需要判断(下一个顶点是否已经染色color[j] == -1
以及 下一个顶点如果已经染色了,那么需要获得下一个顶点染色的递归结果)
时间复杂度
首先对每个顶点会在main
函数里遍历一次。
然后对于每一条边,再每个顶点遍历的时候至多会遍历一次。
所以总共时间复杂度$O(n + m)$
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int u, int c){
color[u] = c;
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (color[j] == -1){
if (!dfs(j, !c)) return false;
}else if (color[j] == c) return false;
}
return true;
}
int main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(color, -1, sizeof color);
for (int i = 1; i <= m; i ++){
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
bool flag = true;
for (int i = 1; i <= n; i ++){
if (color[i] == -1)
if (!dfs(i, 1)) {
flag = false;
break;
}
}
if (!flag) puts("No");
else puts("Yes");
return 0;
}