Redundant Connection

Q: 冗余连接的时间复杂度是多少？

并查集只需遍历 n 条边一次即可解决问题：时间复杂度为 O(n · α(n))，其中 α(n) 在实际应用中最多为 4，空间复杂度为 O(n)。剥离叶节点的时间复杂度也是 O(n)。每次移除后都重新搜索，时间复杂度则为 O(n²)。

中等并查集图

+10

一个网络最初是一棵树：有 n 个节点，编号从 1 到 n，由 n-1 条无向边连接，且没有环。然后，在两个没有直接相连的节点之间又添加了一条边，因此列表 edges 现在包含 n 条边，并且恰好有一个环。

返回一条可以移除的边，使其余 n-1 条边重新构成一棵树。如果有多条边都符合条件，则返回 edges 中最后出现的那条，按其中原样写出的 [a, b] 形式返回。

函数

findRedundantConnection(edges: integer-2d-array) → integer-array

edgesinteger-2d-array: 这 n 条无向边，每条边都是一对节点 [a, b]，节点编号从 1
返回值integer-array: 在 edges 中最后出现的循环边，写法与其中一致

约束条件

3 ≤ n ≤ 5000，其中 n = edges.length
edges[i] = [a, b]，其中 1 ≤ a, b ≤ n 且 a ≠ b
没有任何一条边会以任一方向重复出现。
这些边连接所有 n 个节点，并且恰好构成一个环。

示例

输入: edges = [[1, 2], [1, 3], [2, 3]]
输出: [2, 3]
解释: 这三条边组成三角形 1、2、3，因此移除其中任意一条都会留下一个树。[2, 3] 在列表中排在最后。

输入: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
输出: [1, 4]
解释: 这个循环是 1、2、3、4、1。边 [1, 5] 不在其中：移除它会使节点 5 断开。在这条循环的四条边中，[1, 4] 最后出现。

进阶

如果这些边是有向的，而且原图是一棵有根树，那么当新增的边导致某个节点有两个父节点时，你会删除哪条边？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

删除一条边后，图恰好变成一棵树的条件是这条边位于图中唯一的环上，因此答案是列表中最后出现的环边。并查集只需遍历一遍即可找到它：按顺序添加边，第一条两端已经连通的边就是答案。

试着逐条移除边，从最后一条开始

结果正确，但无法在最大的测试中运行完毕

思路

移除一条边，并检查其余 n-1 条边是否构成一棵树。对于 n 个节点和 n-1 条边，只有从节点 1 开始的一次搜索能够到达全部 n 个节点时，它们才构成一棵树。从列表末尾开始尝试这些边，这样第一个通过检查的移除方案就是最靠后的那个。将每条边的索引存储在邻接列表中，搜索时可以跳过被移除的边，无需重建任何内容。

每次尝试都需要进行一次完整的 O(n) 搜索，而尝试次数最多为 n：当 n = 5000 时，最多需要 2.5 × 10^7 步。

算法

构建邻接表，为每个邻居保存通向它的边的索引。
让 skip 从最后一个索引递减到 0，从节点 1 开始搜索，并忽略索引为 skip 的边。
统计搜索到的节点数。
如果搜索到所有 n 个节点，就返回 edges[skip]。

def findRedundantConnection(edges):
    n = len(edges)
    # graph[x] holds (neighbour, index of the edge) for every edge at node x.
    graph = [[] for _ in range(n + 1)]
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, i))
        graph[v].append((u, i))
    # Try leaving out each edge, the last one first.
    for skip in range(n - 1, -1, -1):
        # Without edge skip, can node 1 still reach all n nodes?
        seen = [False] * (n + 1)
        seen[1] = True
        stack = [1]
        reached = 1
        while stack:
            node = stack.pop()
            for nxt, i in graph[node]:
                if i != skip and not seen[nxt]:
                    seen[nxt] = True
                    reached += 1
                    stack.append(nxt)
        # n-1 edges that connect n nodes form a tree.
        if reached == n:
            return edges[skip]
    return []

剥下叶子

思路

叶子是只有一条边的节点，不可能位于环上，因为环上的每个节点都有一条边进入，也有一条边离开。移除叶子后，它的相邻节点可能变成叶子，所以要不断剥离，直到没有叶子为止。剩下的正好是环，因为环上的每个节点都保留着环上的两条边。在第二个示例中，节点 5 被剥离，节点 1 保留两条边，节点 1 到 4 留了下来。

两个剩余节点之间的任何边都是环上的边，因为环上节点之间再有一条连接，就会形成第二个环。因此，从末尾开始扫描 edges，并返回两个端点都仍然存在的第一条边。

算法

构建邻接表，并统计每个节点的度数。
将所有度数为 1 的节点压入栈中。
弹出一个叶节点，将其度数设为 0，并降低其剩余邻居的度数；当该邻居的度数降为 1 时，将其压入栈中。
栈为空时，度数大于 0 的节点构成环。
从末尾开始扫描 edges，返回两端都仍在环中的第一条边。

def findRedundantConnection(edges):
    n = len(edges)
    graph = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1
    # A node with one edge cannot lie on the cycle. Remove it, and repeat.
    stack = [x for x in range(1, n + 1) if degree[x] == 1]
    while stack:
        leaf = stack.pop()
        degree[leaf] = 0
        for nxt in graph[leaf]:
            if degree[nxt] > 0:
                degree[nxt] -= 1
                if degree[nxt] == 1:
                    stack.append(nxt)
    # Only the cycle is left. Its edge that comes last in the list is the answer.
    for u, v in reversed(edges):
        if degree[u] > 0 and degree[v] > 0:
            return [u, v]
    return []

并查集：第一条形成环的边

思路

按列表顺序添加边，并跟踪哪些节点相连。在环闭合之前，每条边都会连接两个彼此之间没有路径的部分。第一条连接已相连节点的边会闭合环。环上的其他边都在它之前添加，因此它是最后出现的环边。在第二个示例中，[1, 4]发现节点 1 和 4 已经相连，而[1, 5]永远不会被读取。

并查集使用一个数组parent；从一个节点沿着指针查找，最终会到达它所在部分的根节点。将较小的部分挂到较大的部分下，并在执行find时让节点指向它们的祖父节点，可以缩短链。这样，每次操作的均摊开销为 O(α(n))，其中 α 是反阿克曼函数，对于任何实际输入都不超过 4。

算法

让从 1 到 n 的每个节点都指向自身，parent[x] = x，并将其大小设为 1。
按顺序遍历 edges。对于 [u, v]，查找 u 的根和 v 的根。
如果两个根相同，[u, v] 就闭合了这个环：按原样返回它。
否则，较大的部分吸收较小的部分：较大部分的根成为较小部分根的父节点，并将两个部分的大小相加。

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))  # every node starts as its own group
    size = [1] * (n + 1)

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # u and v are already connected: this edge closes the cycle.
        if a == b:
            return [u, v]
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return []

易错点和边界情况

返回列表的最后一条边。在第二个示例中，这条边是 [1, 5]，移除它会让节点 5 断开。
剥离后从前面开始扫描。这样会返回最早的环边，在第二个示例中是 [1, 2]。
对边排序或调换顺序。如果列表中是 [3, 1]，就返回 [3, 1]，而不是 [1, 3]。
为节点 0 到 n-1 分配数组。节点从 1 开始编号，因此节点 n 需要一个有 n+1 个槽位的数组。
沿着环递归。递归可能经过全部 5000 个节点，是 Python 默认递归限制的 5 倍，因此请在 find 中使用显式栈和循环。

常见问题3

冗余连接的时间复杂度是多少？

并查集只需遍历 n 条边一次即可解决问题：时间复杂度为 O(n · α(n))，其中 α(n) 在实际应用中最多为 4，空间复杂度为 O(n)。剥离叶节点的时间复杂度也是 O(n)。每次移除后都重新搜索，时间复杂度则为 O(n²)。

删除哪些边可以留下一个树？

恰好是环上的边。每条边的两个端点之间，都能沿着环的其余部分找到另一条路径，因此移除这条边后，图仍然连通。其他任何边都是连接图中两个部分的唯一通道，移除它就会使这两个部分分开。

可以用 DFS 解决冗余连接问题吗？

是的。添加每条边之前，从一端开始沿着目前已添加的边进行搜索；第一条另一端已经可达的边就是答案。每条边需要 O(n) 时间，总共需要 O(n²) 时间，而并查集能以近乎恒定的时间回答同样的问题。

def findRedundantConnection(edges):
    # 在这里编写代码

测试 #1

测试 #2

参数

edges = [[1, 2], [1, 3], [2, 3]]

预期输出

[2, 3]