图

tips

并查集

并查集是管理元素所属集合的的森林，主要操作是查询 & 合并

主要场景: 无向图连通性 找环

通常用于判定是否同属一集

• 合并: 合并两个元素所属的集
• 查询: 查询某个元素所属的集(查询树的根节点)

初始化: 每个元素都属于一个单独的集合，父亲都设置为自己
查询: 找最终的父节点
合并: 将一棵树连在另一颗树上
删除: 将节点的父节点设置为自己

class UnionFind {

    private final int[] parent;

    public UnionFind(int n) {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    private int find(int idx) {
        if (parent[idx] != idx)
            parent[idx] = find(parent[idx]);
        return parent[idx];
    }

    private void union(int idx1, int idx2) {
        int x = find(idx1);
        int y = find(idx2);
        parent[y] = x;
    }
}

图的中心

310. 最小高度树 mid

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 $edges[i]=[a_i,b_i]$ 表示树中节点 $a_i$ 和 $b_i$ 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

思路 1

随便找 1 个节点，从该节点开始找最长路的终点 x, 再从 x 出发找最长路的终点 y, x,y 的中点就是 root
如何证明正确性？为什么能覆盖所有的 root?

思路 2 BFS

找到所有叶子结点(入度=1)，然后向中间 BFS, 最后一波的就是

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] bridges) {
        if (n == 1) return List.of(0);
        List<Integer>[] edges = new List[n];
        int[] in = new int[n];
        for (int[] edge : bridges) {
            int a = edge[0];
            int b = edge[1];
            in[a]++;
            in[b]++;
            if (edges[a] == null) edges[a] = new ArrayList<>();
            if (edges[b] == null) edges[b] = new ArrayList<>();
            edges[a].add(b);
            edges[b].add(a);
        }
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < in.length; i++) {
            if (in[i] == 1) {
                que.add(i);
                in[i]--;
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!que.isEmpty()) {
            int size = que.size();
            res.clear();
            while (size-- > 0) {
                Integer node = que.remove();
                res.add(node);
                for (Integer i : edges[node]) {
                    if (in[i] == 0) continue;
                    if (--in[i] == 1) que.add(i);
                }
            }
        }
        return res;
    }
}

找环

找环考虑并查集和拓扑排序

684. 冗余连接 mid

剑指 Offer II 118. 多余的边

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1 ～ n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，$edges[i]=[a_i,b_i]$ 表示图中在 $a_i$ 和 $b_i$ 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

解法 并查集

所有的节点都应当在一个群，遍历边集，如果 find 存在连接就是冗余边，否则将节点 union

class Solution {

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            // 后加的2个点同属一个parent
            if (uf.find(node1) != uf.find(node2)) uf.union(node1, node2);
            else return edge;
        }
        return new int[]{};
    }

    static class UnionFind {

        private final int[] parent;

        public UnionFind(int n) {
            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }

        private int find(int idx) {
            if (parent[idx] != idx)
                parent[idx] = find(parent[idx]);
            return parent[idx];
        }

        private void union(int idx1, int idx2) {
            int x = find(idx1);
            int y = find(idx2);
            parent[y] = x;
        }
    }
}

二分图

如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么这个图就是二分图。

二分图不存在长度为奇数的环
因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。

785. 判断二分图 mid

存在一个 无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

• 不存在自环（graph[u] 不包含 u）。
• 不存在平行边（graph[u] 不包含重复值）。
• 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
• 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图。

如果图是二分图，返回 true; 否则，返回 false。

解法 DFS

直接染色

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] colors = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (colors[i] == 0 && !isBipartite(colors, graph, i, 1)) {
                return false;
            }
        }
        return true;
    }

    private boolean isBipartite(int[] colors, int[][] graph, int i, int c) {
        if (colors[i] != 0) return colors[i] == c;
        colors[i] = c;
        for (int g : graph[i]) {
            if (!isBipartite(colors, graph, g, -c)) return false;
        }
        return true;
    }
}