3、染色法判定二分图

AcWing 860. 染色法判定二分图

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int n, m;
    int N = 2000010;
    int h[] = new int[N];
    int e[] = new int[N];
    int ne[] = new int[N];
    int idx;

    int color[] = new int[N];

    void insert(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    boolean dfs(int start, int c) {
        color[start] = c;
        boolean flag = true;
        for (int i = h[start]; i != -1; i = ne[i]) {
            int j = e[i];
            if (color[j] == -1) {
                flag &= dfs(j, 3 - c);
            } else if (color[j] != 3 - c) {
                return false;
            }
        }
        return flag;
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Arrays.fill(color, -1);
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            insert(a, b);
            insert(b, a);
        }
        boolean flag =true;
        for (int i = 1; i <= n; i++) {
            if(color[i]==-1){
                flag &= dfs(i, 1);
                if(flag==false) break;
            }

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