二分图

https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E5%9B%BE

在图论中，二分图是一类特殊的图，又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。

题目：

剑指 Offer II 106. 二分图

886. 可能的二分法

染色法

在还没有被染色的点开始DFS，对其相邻的点染不同的颜色，如果和相邻的点颜色相同，就一定不是二分图。

$O(n+m)$

class Solution {
    int[] color;
    boolean ans = true;
    int n;

    public boolean isBipartite(int[][] graph) {
        n = graph.length;
        color = new int[n];
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                color[i] = 1;
                dfs(graph, i);
            }
        }
        return ans;
    }

    public void dfs(int[][] graph, int idx) {
        for (int next : graph[idx]) {
            if (color[next] == 0) {
                color[next] = color[idx] == 1 ? 2 : 1;
                dfs(graph, next);
            } else if (color[next] == color[idx]) {
                ans = false;
                return;
            }
        }
    }
}

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (color[i] == 0) {
                color[i] = 1;
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                while (!q.isEmpty()) {
                    int size = q.size();
                    while (size-- > 0) {
                        int now = q.poll();
                        for (int next : graph[now]) {
                            if (color[next] == 0) {
                                color[next] = color[now] == 1 ? 2 : 1;
                                q.offer(next);
                            } else if (color[next] == color[now]) return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

匈牙利算法

1820. 最多邀请的个数

求二分图的最大匹配数和最小点覆盖数。

$O(nm)$

class Solution {
    public int maximumInvitations(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int n = grid.length; // boy
        int m = grid[0].length; // girl
        int ans = 0;
        int[] matched = new int[m]; // 女孩匹配的男孩
        Arrays.fill(matched, -1);
        // 男孩尝试去约女孩
        for (int i = 0; i < n; i++) {
            boolean[] invited = new boolean[m]; // 女孩有没有被约
            if (check(grid, i, matched, invited, m)) {
                ans++;
            }
        }
        for (int i : matched) {
            System.out.print(i + " ");
        }
        return ans;
    }

    public boolean check(int[][] grid, int boyIndex, int[] matched, boolean[] invited, int m) {
        for (int i = 0; i < m; i++) {
            // 这个女孩没有被约，并且这个男孩可以约这个女孩
            if (!invited[i] && grid[boyIndex][i] == 1) {
                // 预先占位(加锁)
                invited[i] = true;
                // 当前女孩还没有匹配到男孩
                // 或者约了这个女孩的男孩可以 约到另外一个女孩
                // 则当前男孩可以和这个女孩匹配
                if (matched[i] == -1 || check(grid, matched[i], matched, invited, m)) {
                    matched[i] = boyIndex;
                    return true;
                }
            }
        }
        return false;
    }
}