Given a set of N people (numbered 1, 2, …, N), we would like to split everyone into two groups of any size.
Each person may dislike some other people, and they should not go into the same group.
Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.
Return true if and only if it is possible to split everyone into two groups in this way.

so the problem is easy to understand actually:
there are a group of nodes, and if they are dislike each other, it will be on int[][] dislike array. for people dislike each other, we should let them in different group
now we need to check if we can divide those group of people into just two.

idea:
use two hashset as graphs, because it’s easy to judge if this node is in this graph or not.
suppose we are in the middle of construct those two graphs, for each new array in dislike, we check if those two are in any of these graph or not, if both of them are not in, then we put them in(but which to which? it will actually effect later we add other nodes that may not compatible with them), so this solution doesn’t work.
now what should we do?

we should construct the graph based on this dislike, and use dfs to iterate the whole graph, and we give current node and it’s neighbor with different color(if this neighbor hasn’t colored yet, but if it is colored, then we need to check if the color is the same with current node, if it is the same, then we can just return false)
but let’s try to write the code in BFS.
but strangely, this BFS solution can’t get accepted but the DFS can:

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        List<Integer>[] graph = new ArrayList[N];
        
        for (int i = 0; i<N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        int m = dislikes.length;
        for (int i = 0; i < m; i++) {
            int node1 = dislikes[i][0] - 1;
            int node2 = dislikes[i][1] - 1;
            
            graph[node1].add(node2); //undirected graph, so we have to add them all
            graph[node2].add(node1);
        }
        
        int[] color = new int[N]; //this is actually like visited
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0); //actually we can start with any node from 0 to N-1
        color[0] = 1; // and we have to pick a color for node 0 too
        
        
        while (!queue.isEmpty()) {
            System.out.println("x");
            int cur = queue.poll();
            int curColor = color[cur];
    
            int size = graph[cur].size();
            for (int i = 0; i < size; i++) {
                int neigh = graph[cur].get(i);
                int neighColor = color[neigh];
                if (neighColor == 0) { //that means we haven't visited it
                    color[neigh] = curColor == 1? -1: 1; //assign new value on color[neigh] instead of neighColor
                    queue.offer(neigh);
                } else { //if we visited it, then we don't have to offer it in the queue again
                    if (neighColor == curColor) {
                        return false;
                    }
                }
                
            }
        }
        return true;
    }
    
    
}

DFS accepted solution:

    public boolean possibleBipartition(int N, int[][] dislikes) {
        List<Integer>[] graph = new ArrayList[N]; //graph is [list1, list2, list3...]
        for (int i = 0; i < N; i++) graph[i] = new ArrayList<>(N); //initialize each one of them, it is not necessary
        for (int i = 0; i < dislikes.length; i++) {
            int a = dislikes[i][0] - 1; //project input to graph we can easily use
            int b = dislikes[i][1] - 1;
            graph[a].add(b);
            graph[b].add(a);
        }
        int[] color = new int[N];
        color[0] = 1;
        for (int i = 0; i < N; i++) {
            if (!dfs(graph, i, color)) return false;
        }
        return true;   
    }
    
    private boolean dfs(List<Integer>[] graph, int node, int[] color) {
        for (int i = 0; i < graph[node].size(); i++) { //for every neighbor of current node
            int op = graph[node].get(i); 
            if (color[op] == 0) { //if it hasn't been colored yet
                color[op] = color[node] == 1 ? 2 : 1; //then we choose the opposite of the node
                if (!dfs(graph, op, color)) return false; //we continue the dfs trip
            } else { //if the neighbor is colored, then we should leave it unless it has the same color as the current node
                if (color[op] == color[node]) return false;
            }
        }
        return true;
    }
}