题目

https://leetcode.com/problems/redundant-connection/

题解

并查集问题

1)有若干个样本a、b、c、d…类型假设是V

2)在并查集中一开始认为每个样本都在单独的集合里

3)用户可以在任何时候调用如下两个方法：

​ boolean isSameSet(V x, V y) : 查询样本x和样本y是否属于一个集合

​ void union(V x, V y) : 把x和y各自所在集合的所有样本合并成一个集合

4）isSameSet和union方法的代价越低越好

并查集

1）每个节点都有一条往上指的指针

2）节点a往上找到的头节点，叫做a所在集合的代表节点

3）查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个

4）把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方即可

并查集的优化

1）节点往上找代表点的过程，把沿途的链变成扁平的

2）小集合挂在大集合的下面

3）如果方法调用很频繁，那么单次调用的代价为O(1)，两个方法都如此

并查集的应用

解决两大块区域的合并问题

常用在图等领域中

本题题解

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        // adjacent matrix
        int[][] edge = new int[1001][1001];
        int N = 0;
        for (int[] pair : edges) {
            N = Math.max(N, Math.max(pair[0], pair[1]));
            edge[pair[0]][pair[1]] = 1;
            edge[pair[1]][pair[0]] = 1;
        }

        // union find
        int[] size = new int[N + 1]; // i所在的集合大小
        Arrays.fill(size, 1);
        int[] parent = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }
        for (int[] pair : edges) {
            int r0 = findRoot(parent, pair[0]);
            int r1 = findRoot(parent, pair[1]);

            if (r0 == r1) return pair;
            // 如果pair[0], pair[1]不在同一集合，则将小集合代表挂在大集合代表下方
            if (size[r0] > size[r1]) {
                parent[r1] = r0;
            } else {
                parent[r0] = r1;
            }
            size[r0] = size[r1] = size[r0] + size[r1];
        }
        return null;
    }

    // 从i开始一直往上，往上到不能再往上，代表节点，返回
    // 这个过程要做路径压缩
    public int findRoot(int[] parent, int i) {
        int cur = i;
        while (cur != parent[cur]) {
            cur = parent[cur];
        }
        while (i != parent[i]) {
            int next = parent[i];
            parent[i] = cur;
            i = next;
        }
        return cur;
    }
}