11-染色法判定二分图

算法思想

二分图

一个图中的节点划分为两个集合，两个集合内部不存在边，则该图为二分图

奇数环

一个图中若没有奇数环，则该图为二分图

染色法

运用染色法，可以判定一个图中是否有奇数环，进而可以判定一个图是否为二分图

算法模板

import java.util.*;

public class Main {
    static int N = 100010, M = 200010;
    static int n, m, idx;
    // color[i]标记 i 号点的所染的颜色
    static int[] e = new int[M], ne = new int[M], h = new int[N], color = new int[N];
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        Arrays.fill(h, -1);
        
        while(m -- > 0)
        {
            int u = in.nextInt(), v = in.nextInt();
            add(u, v);
            add(v, u);
        }
        // 即使图不连通，
        // 尝试从每一个节点开始染色，
        // 仍可确定图中是否存在奇数环
        boolean flag = true;
        for(int i = 1; i <= n; i ++ )
        {
            if(color[i] == 0)
            {
                if(!dfs(i, 1))
                {
                    flag = false;
                    break;
                }
            }
        }
        
        var res = flag ? "Yes" : "No";
        System.out.println(res);
    }
    
    static void add(int u, int x)
    {
        e[idx] = x;
        ne[idx] = h[u];
        h[u] = idx ++ ;
    }
    
    // 有两种颜色，颜色1和颜色2
    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)
            {
                // 为 u 号点的相邻节点，染上 另一种颜色 3 - c
                if(!dfs(j, 3 - c)) return false;
            }
            else if(color[j] == c) return false;
        }
        return true;
    }
}