二分图-染色法-dfs

1.判断一个图是否是二分图当且仅当图中不包含奇数环
2. dfs当前边为1 他的临边为2 看是否满足条件
3. 注意图有可能不是连通图

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;public class BinaryGraph {private static int N = 100010;//还没有进行初始化！private static int[] h = new int[N];private static int[] e = new int[N];private static int[] ne = new int[N];private static int idx;private static  int[] colors = new int [N];private static int n;private static int m;private static boolean flag = true;public static void add(int a, int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;}public static boolean dfs(int a, int c){colors[a] = c;for(int i = h[a]; i != -1; i = ne[i] ){int j = e[i];//如果没有对这个点进行染色if(colors[j] == 0){dfs(j,3 - c);}else if(colors[j] == c){flag = false;return false;}}return true;}public static void main(String[] args) throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));String[] s = reader.readLine().split(" ");n = Integer.parseInt(s[0]);m = Integer.parseInt(s[1]);Arrays.fill(h,-1); //对h进行初始化for(int i = 0; i < m; i++){String[] s1 = reader.readLine().split(" ");int u = Integer.parseInt(s1[0]);int v = Integer.parseInt(s1[1]);//无向图add(u,v);add(v,u);}for(int i = 1; i <= n; i++){//当前点没有被染色if(colors[i] == 0){//染色时出现冲突if(!dfs(i,1)){flag = false;break;}}}if(flag){System.out.println("Yes");}else System.out.println("No");}
}