题目：染色法判定二分图

解题思路：

使用染色法判断二分图的思路就是对每个节点进行2染色，
如果存在某个节点的邻接节点与它染的颜色相同，那这张图就不是二分图

时间复杂度分析：
染色法判断二分图的时间复杂度为O(n+mn+m),其中n为节点数量，m为边的数量。

JAVA 代码 dfs解法一

import java.util.*;
import java.io.*;

class Main{
    static int N = 100010, M = 2*N, idx,n,m;
    //判断某个点是否被染过了颜色 1表示白色，2表示黑色
    static int[] color = new int[N], h = new int[N];
    static int[] e = new int[M], ne = new int [M];

    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    //用于判断某个图是不是二分图
    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 ){
                //如果相邻的节点染了同样的颜色，说明不是二分图，返回false
                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 = false;
        for(int i=1; i<=n; i++){
            if(color[i] !=0 )continue;
            if(!dfs(i,1)){
                flag = true;
                break;
            }
        }
        if(flag)System.out.println("No");
        else System.out.println("Yes");

    }
}

JAVA 代码 bfs解法二

import java.util.*;
import java.io.*;

class Main{
    static int N = 100010, M = 2*N, n,m, idx;
    static int[] color = new int[N], h = new int[N];
    static int[] e = new int[M], ne = new int[M];

    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    //就此处有变动, dfs 转成 bfs.
    static boolean bfs( int u){
        color[u] = 1;
        Queue<Integer > q=  new LinkedList<>();
        q.add(u);

        while(!q.isEmpty()){
            int t = q.poll();

            for(int i=h[t]; i!=-1;i=ne[i]){
                int j = e[i];

                //未上过色的点
                if(color[j] == 0){
                    //转换每个点的color
                    color[j] = 3-color[t];
                    //把该点加入队列.
                    q.add(j);

                //如果上过色. 则判断是否和上层点的颜色一样
                }else if(color[j] == color[t]) 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 = false;

        for(int i=1; i<=n; i++){
            if(color[i] != 0) continue;
            if(!bfs(i)){
                flag = true;
                break;
            }
        }

        if(flag ) System.out.println("No");
        else System.out.println("Yes");
    }
}