题解 | #幼儿园分班#

//其实就是判断是不是二分图，直接用染色法就好了
import java.util.*;

public class Main{

    static int n, m, N = 1000, M = 2 * 1000, idx;
    static int[] h = new int[N], e = new int[M], ne = new int[M];
    static int[] color = new int[N];
    static void add(int a, int b) {
       e[idx] = b;
       ne[idx] = h[a];
       h[a] = idx ++;
    }
    public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       n = in.nextInt(); m = in.nextInt();
       Arrays.fill(h, -1);
       for(int i = 1; i <= m; i ++) {
          int a = in.nextInt(), b = in.nextInt();
          add(a, b); add(b, a);
       }

       boolean flag = dfs(1, 1);
       if(flag == true)
           System.out.println(1);
       else
           System.out.println(0);


    }
    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){
                if(!dfs(j, -c))
                    return false;
            }else if(color[j] == c)
                return false;
        }
        return true;
    }

}