【模板】二分图判定

import java.util.*;
import static java.lang.System.in;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        int m  = sc.nextInt();
        // 建图
        HashMap<Integer, HashSet<Integer>> graph =new HashMap<>();
        
        for(int i = 0; i<m; i++){
            int curr = sc.nextInt();
            int next = sc.nextInt();
            graph.putIfAbsent(curr,new HashSet());
            graph.get(curr).add(next);
        }
        //  是n+1,因为从0开始
        int[] colors = new int[n+1];
        // 我们染色三种情况，0是没有染色到，1是一种颜色，-1是一种颜色
        boolean ans = true;
        for(int cur= 1; cur<=n; cur++){
            //对于一个从来没染过色的点，初始都为1，然后我们开始爱的魔力找圈圈
            if(colors[cur] == 0  &&  !dfs(colors,1,graph, cur ))  ans =false;
        }
        //***改的，就是为了输出简单
        String res = "Yes";
        if(!ans)  res = "No";
        
        System.out.println(res);
    }
    private static boolean dfs(int[] colors, int color, HashMap<Integer, HashSet<Integer>> graph,int cur){
       //找到了一个环，然后看他现在要给的颜色和之前的颜色是不是一样的。这个根据题意好理解。
        if(colors[cur] != 0) return colors[cur] == color;
        colors[cur] = color;
        
        //非连通图的情况，到了尾巴，发现他是个一条边，这种情况肯定是对的
        if(!graph.containsKey(cur)) return true;
        
        for(int next:  graph.get(cur)){
            if(!dfs(colors, -color, graph, next)) return false;
        }
        
        return true;
    }
}