684. 冗余连接

Problem: 684. 冗余连接，记录官解题解。

思路

这题一开始尝试的时候，我就想到的也是用集合的方法来做，尝试了用集合列表，每个节点赋值一个集合。但是提交时有一些用例过不了，排查后发现，这些节点可能共同属于一个集合，但是却被赋予了不同的集合，调试了许久也没有调试出来。后来看题解才恍然大悟，用的正是并查集（记得刚接触算法就对这个数据结构特别有印象，但是确实很久没有遇到了）。

使用并查集即可完成，遍历数组，先查看边上的两个节点是否属于同一个集合，如果是的话，则把答案设为当前边。否则，将边上的两个节点都加入同一个集合。

并查集

这里顺便复习一下并查集的知识，以防再次遗忘。

首先在数据结构方面，并查集是一个树形结构，有两个操作：union和find。分别是合并两个集合，查找一个集合的根节点，即判断所属的最大集合。

一般情况下，可以用parent数组来存储所有节点的直接父亲节点。节点之间构成树形结构。

初始化并查集时，把每个结点的parent都设为自己，即用自己来标记集合。

合并两个并查集时，将一个节点的根节点的parent设为另一个节点的根节点，这样就把整个集合移动到了另一个集合下。想象成树形结构就很好理解了。

复杂度

• 时间复杂度: $O(nlogn)$
• 空间复杂度: $O(n)$

Code

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (find(parent, node1) != find(parent, node2)) {
                union(parent, node1, node2);
            } else {
                return edge;
            }
        }
        return new int[0];
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
}