冗余连接

难度:

标签:

题目描述

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

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [a_i, b_i] 表示图中在 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 中无重复元素
给定的图是连通的

代码结果

运行时间: 22 ms, 内存: 16.3 MB

/*
 * 题目思路：
 * 通过 Java Stream 实现类似功能。
 * 由于 Java Stream 不直接支持并查集的实现，
 * 我们还是需要手动维护并查集结构，但可以使用 Stream 来简化部分逻辑。
 */
import java.util.Arrays;
public class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        Arrays.setAll(parent, i -> i); // 初始化并查集
        return Arrays.stream(edges).filter(edge -> {
            int u = edge[0], v = edge[1];
            int pu = find(parent, u);
            int pv = find(parent, v);
            if (pu != pv) {
                parent[pu] = pv;
                return false;
            }
            return true;
        }).findFirst().orElse(new int[0]); // 返回第一个检测到的附加边
    }
    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
}

解释

方法:

本题解使用了并查集算法。我们遍历每条边，将边的两个顶点所在的连通分量进行合并。如果遇到一条边的两个顶点已经属于同一个连通分量，那么说明这条边的出现会导致环路，因此它就是我们要找的那条多余的边。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么并查集可以用来确定图中的冗余连接？

▷

并查集是一种特殊的数据结构，用于高效地处理动态连通性问题。在处理图的冗余连接问题时，我们可以利用并查集来跟踪每个顶点所属的连通分量。通过遍历图中的每条边，我们尝试将边的两个顶点合并到同一个连通分量中。如果在尝试合并前，两个顶点已经属于同一连通分量，这表明添加这条边会形成一个环，因此这条边就是冗余的。这种方法有效地利用了并查集维护连通分量的特性，可以在较低的时间复杂度内判断并找出图中的冗余连接。

🦆

在并查集的实现中，路径压缩的具体作用是什么？它是如何优化查找效率的？

▷

路径压缩是并查集优化技术之一，主要用来减少查找根节点时的时间复杂度。具体来说，路径压缩在每次查找过程中，将查找路径上的每个节点直接连接到根节点。这样做的结果是，未来对同一连通分量内任一节点的查找操作都可以更快地到达根节点，因为路径被大大缩短了。通过路径压缩，可以将并查集的时间复杂度优化到接近常数时间，从而提高整个算法的效率。

🦆

题解中提到返回数组edges中最后出现的那个冗余边，这种处理方法是否总是有效？

▷

是的，这种处理方法总是有效的。在题目设定中，图中只有一个冗余连接，这意味着图是一个几乎是树的结构，只多了一条边导致成环。因此，当我们按顺序处理边时，最后一个在并查集中检测到已经处于同一连通分量的边，必定是导致环的冗余边。因为如果先出现的边是冗余的，那么后面的边就不会形成环。所以，按照题解的方法处理，总能正确返回最后出现的那个冗余连接。

🦆

在并查集中，节点初始化为自己是父节点的理由是什么？

▷

在并查集中，每个节点初始化为自己是父节点的目的在于表示每个节点最初是独立的连通分量。这种初始化方式简单且直观，表明在开始时，没有任何两个节点是相连的，即每个节点自成一个连通分量。随着算法的进行，某些节点会被合并到同一个连通分量中，但初始化时，每个节点作为自己的父节点是表示它们的独立性和初始状态。这是并查集构建其数据结构的基础。

相关问题

冗余连接 II

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。每个元素是一对 [u_i, v_i]，用以表示有向图中连接顶点 u_i 和顶点 v_i 的边，其中 u_i 是 v_i 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

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

提示：

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= u_i, v_i <= n

账户合并

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

示例 1：

输入：accounts = [["John", "[email protected]", "[email protected]"], ["John", "[email protected]"], ["John", "[email protected]", "[email protected]"], ["Mary", "[email protected]"]]
输出：[["John", '[email protected]', '[email protected]', '[email protected]'],  ["John", "[email protected]"], ["Mary", "[email protected]"]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "[email protected]"。 
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'[email protected]']，['John'，'[email protected]']，
['John'，'[email protected]'，'[email protected]'，'[email protected]']] 也是正确的。

示例 2：

输入：accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
输出：[["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]

提示：

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] 由英文字母组成
accounts[i][j] (for j > 0) 是有效的邮箱地址

K 个关闭的灯泡冗余连接 II