发表于 2024.04.10

• 并查集的模板题目，思路类似于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 题目链接