题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个图，说这原来是个树（没闭环），后来加了一条边才变成了现在的图，请遍历边集并找出那个冗余的边，如果有多个答案，取靠后的。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n+1))

        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1:int, index2:int):
            parent[find(index1)] = parent[find(index2)]

        ans = []
        for node1, node2 in edges:
            if find(node1) != find(node2):
                union(node1, node2)
            else:
                ans = [node1, node2]
        return ans