二分图：匹配、染色与网络流

public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n];   // 0=未染色, 1=红, -1=蓝

    for (int i = 0; i < n; i++) {
        if (color[i] != 0) continue;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        color[i] = 1;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph[u]) {
                if (color[v] == 0) {
                    color[v] = -color[u];
                    queue.offer(v);
                } else if (color[v] == color[u]) {
                    return false;   // 同色相邻 → 不是二分图
                }
            }
        }
    }
    return true;
}

public int hungarian(List<Integer>[] graph, int nLeft, int nRight) {
    int[] matchR = new int[nRight];   // 右部节点的匹配对象
    Arrays.fill(matchR, -1);
    int result = 0;

    for (int u = 0; u < nLeft; u++) {
        boolean[] visited = new boolean[nRight];
        if (dfs(graph, u, visited, matchR)) {
            result++;
        }
    }
    return result;
}

private boolean dfs(List<Integer>[] graph, int u, boolean[] visited, int[] matchR) {
    for (int v : graph[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        // v 未匹配，或者 v 的当前匹配对象能找到别的
        if (matchR[v] == -1 || dfs(graph, matchR[v], visited, matchR)) {
            matchR[v] = u;
            return true;
        }
    }
    return false;
}