/**
 * 本质：是不是二部图
 * 时间复杂度O(V + E)（图的DFS和BFS时间复杂度都是O(V + E)）
 * Runtime: 11 ms, faster than 97.38%
 * Memory Usage: 46.7 MB, less than 84.82%
 */
class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] adjacency = new List[n];
        for (int i = 0; i < adjacency.length; i++) {
            adjacency[i] = new ArrayList<>();
        }
        for (int[] pair : dislikes) { // 构造无向图的邻接矩阵
            adjacency[pair[0] - 1].add(pair[1] - 1);
            adjacency[pair[1] - 1].add(pair[0] - 1);
        }
        
        Integer[] colored = new Integer[n]; // 记录涂色情况
        for (int i = 0; i < colored.length; i++) {
            if (colored[i] == null) { // 给没涂色的顶点涂色
                if (!helper(adjacency, i, colored, 1)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean helper(List<Integer>[] adjacency, int i, Integer[] colored, int color) {
        if (colored[i] == null) {
            colored[i] = color;
            for (int next : adjacency[i]) {
                if (!helper(adjacency, next, colored, -color)) {
                    return false;
                }
            }
        } else {
            if (colored[i] != color) {
                return false;
            }
        }
        return true;
    }
}