JZX轻语：简

LeetCode 684 - 冗余连接

发表于2024年04月10日

#并查集 #Krustal算法

并查集的模板题目，思路类似于Krustal算法，先依次添加这些边到并查集, 然后某个边加入后形成了一个环, 则直接return即可。

class DSU:
    def __init__(self, n):
        self.pa = [i for i in range(n)]

    def find(self, x: int) -> int:
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def union(self, x: int, y: int):
        self.pa[self.find(x)] = self.find(y)


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        dsu = DSU(len(edges) + 1)

        for edge in edges:
            u, v = edge
            if dsu.find(u) == dsu.find(v):
                return edge
            dsu.union(u, v)

        return []

闪念标签：LC

题目链接：https://leetcode.cn/problems/redundant-connection/