684. 冗余连接

难度中等

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

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

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

示例 1：

输入: edges = [[1,2], [1,3], [2,3]]

输出: [2,3]

示例 2：

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]

输出: [1,4]

提示:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• edges 中无重复元素
• 给定的图是连通的

# 并查集

我们用 father 数组表示第 i（下标） 个节点的父节点为 father [i]

• 每个节点的父节点初始化为自身

father : [1, 2, 3, 4, 5, ...]

index : [1, 2, 3, 4, 5, ...]

对于每一条边 [u, v]，我们规定从 v -> u（也可以 u -> v）

• 即：将无向图看作是有向图，且 v 指向 u

不断寻找 u 的父节点与 v 的父节点，将 v 的父节点指向 u 的父节点

# 图解并查集

若轮播图加载不出来，请刷新

# 路径压缩说明

若轮播图加载不出来，请刷新

# 小结

其实说白了就是找每个节点的根节点，就不不断地寻找父节点

并查集可以理解为找爹的过程：

• 查找：找自己爹是谁
• 归并：让自己的爹找一个新爹，并且新爹不是任何人的儿子

# 代码

答案可能有多条边，但题目要求返回二维数组中的最后一条边。但并查集正序遍历 edges 数组，为什么查出来的第一条边就肯定会是题目要求的最后一条边呢？

• 题目的意思，这个图一定只有 1 个环
• 如果有两个环的话，删除一条边不可能形成一颗树

class Solution {

    public int[] findRedundantConnection(int[][] edges) {

        int n = edges.length;

        // 初始化，自身节点为父节点

        father = new int[n + 1];

        for (int i = 0; i < n; i++) {

            father[i] = i;

        }

        // 对每个集合进行合并，这里统一前者指向后者

        for (int i = 0; i < n; i++) {

            // 合并

			if (union(edges[i][0], edges[i][1])) {

                return edges[i];

            };

        }

        return null;

    }

    int[] father;

	public boolean union(int x, int y) {

        int l = findRoot(x);

        int r = findRoot(y);

        // 二者的根节点相同，说明这是一条路径，再加上二者直连的路径，形成环路

        if (l == r) {

            return true;

        }

        // 前者指向后者，合并的操作

        father[l] = r;

        return false;

    }

    // 找根节点

    public int findRoot(int i) {

        if (father[i] == i) {

            return i;

        }

        int ancestor = findRoot(father[i]);

        // 路径压缩

        father[i] = ancestor;

        return ancestor;

    }

}