题目描述
给定一个n个点m条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n和m。
接下来m行,每行包含两个整数u和v,表示点u和点v之间存在一条边。
输出格式
如果给定图是二分图,则输出“Yes”,否则输出“No”。
数据范围
1≤n,m≤105
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes
思路
二分图 当且仅当图中不含奇数环
通过深度遍历的方式,进行交叉染色,也可以采用广度遍历的方式,进行不同层的染色
1
_____|_____
| |
2 2
|
1
由于存在不同连通块区域, 需要遍历每个点,因为染色的方式是基于连通块的某个点进行遍历的,时间复杂度为O(n + m);
java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 100010, M = 200010;
static int n, m;
static int[] h = new int[N], e = new int[M], ne = new int[M];
static int idx;
static int[] color = new int[N];
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
private static boolean dfs(int u, int c) {
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (color[j] == 0) {
if (!dfs(j, 3 - c)) return false;
} else if (color[j] == c) return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);
while (m -- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
add(b, a);
}
boolean flag = true;
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
if (flag) System.out.println("Yes");
else System.out.println("No");
}
}
C++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200020;
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 != -1; i = ne[i]){
int j = e[i];
if(!color[j]){ //c=1 3-c=2 c=2 3-c = 1
if(!dfs(j, 3 - c)) return false;
}
//待染色的点和记录的当前点颜色一样。
else if (color[j] == c) return false;
}
return true;
}
int main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m --){
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]){ //未染色
if(!dfs(i, 1)){ //开始对以节点i为根的连通块染成1
flag = false;
break;
}
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}