二分图

具体定义见传送门

利用染色的思路去解题

785. 判断二分图

// dfs
private boolean ok = true;
public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    // visited[i] = 0 : 未染色 ; 1 : red ; -1 : blue
    int[] visited = new int[n];
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            dfs(graph, visited, i, 1);
        }
    }
    return ok;
}
private void dfs(int[][] graph, int[] visited, int v, int color) {
    if (!ok) return ;
    visited[v] = color;
    for (int i : graph[v]) {
        // 未染色
        if (visited[i] == 0) {
            dfs(graph, visited, i, (-1) * color);
        } else {
            if (visited[i] == visited[v]) {
                ok = false;
            }
        }
    }
}

// bfs
private boolean ok = true;
public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    // visited[i] = 0 : 未染色 ; 1 : red ; -1 : blue
    int[] visited = new int[n];
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            bfs(graph, visited, i);
        }
    }
    return ok;
}
private void bfs(int[][] graph, int[] visited, int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = 1;
    while (!queue.isEmpty() && ok) {
        int v = queue.poll();
        for (int i : graph[v]) {
            if (visited[i] == 0) {
                visited[i] = visited[v] * (-1);
                queue.offer(i);
            } else {
                if (visited[i] == visited[v]) {
                    ok = false;
                }
            }
        }
    }
}

886. 可能的二分法

private boolean ok = true;
public boolean possibleBipartition(int n, int[][] dislikes) {
    List<Integer>[] graph = buildGraph(n, dislikes);
    int[] visited = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) dfs(graph, visited, i, 1);
    }
    return ok;
}
private List<Integer>[] buildGraph(int n, int[][] dislikes) {
    List<Integer>[] graph = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) {
        graph[i] = new ArrayList<Integer>();
    }
    int m = dislikes.length;
    for (int i = 0; i < m; i++) {
        graph[dislikes[i][0]].add(dislikes[i][1]);
        graph[dislikes[i][1]].add(dislikes[i][0]);
    }
    return graph;
}
private void dfs(List<Integer>[] graph, int[] visited, int p, int color) {
    if (!ok) return ;
    visited[p] = color;
    for(int i : graph[p]) {
        if (visited[i] == 0) {
            dfs(graph, visited, i, color * (-1));
        } else {
            if (visited[i] == visited[p]) ok = false;
        }
    }
}