684.冗余连接

链接：684.冗余连接
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、图
简介：输入一个图，该图由一个有着 N 个节点 (节点值不重复 1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间，这条附加的边不属于树中已存在的边。返回一条可以删去的边，使得结果图是一个有着 N 个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

题解 1 - typescript

• 编辑时间：2021-01-13
• 执行用时：96ms
• 内存消耗：45.3MB
• 编程语言：typescript
• 解法介绍：利用 set 储存遍历结果。

function findRedundantConnection(edges: number[][]): number[] {
  const map = new Map<number, Set<number>>();
  let ans: number[][] = [];
  for (const edge of edges) {
    const [num1, num2] = edge;
    const set1 = map.get(num1);
    const set2 = map.get(num2);
    if (set1 && set2 && set1 !== set2) {
      const set = new Set([...set1, ...set2]);
      set.forEach(v => map.set(v, set));
    } else if (!set1 && !set2) {
      const set = new Set([num1, num2]);
      map.set(num1, set);
      map.set(num2, set);
    } else if (!set1 && set2) {
      set2.add(num1);
      map.set(num1, set2);
    } else if (set1 && !set2) {
      set1.add(num2);
      map.set(num2, set1);
    } else {
      ans.push(edge);
    }
  }
  return ans.pop()!;
}

题解 2 - typescript

• 编辑时间：2021-04-30
• 执行用时：92ms
• 内存消耗：40.9MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function findRedundantConnection(edges: number[][]): number[] {
  const uf = new UnionFind(edges.length);
  for (const edge of edges) {
    const [node1, node2] = edge;
    if (uf.same(node1, node2)) return edge;
    uf.union(node1, node2);
  }
  return [];
}

题解 3 - undefined

• 编辑时间：2024-10-27
• 执行用时：3ms
• 内存消耗：17MB
• 编程语言：undefined
• 解法介绍：unionfind。

class UnionFind:
    def __init__(self, n) -> None:
        self.n = n
        self.data = [i for i in range(0, n)]
        self.sizes = [1] * n
        self.cnt = n
    def size(self, v: int) -> int:
        return self.sizes[self.find(v)]
    def find(self, v: int) -> int:
        if self.data[v] != v:
            self.data[v] = self.find(self.data[v])
        return self.data[v]
    def uni(self, v1: int, v2: int):
        p1 = self.find(v1)
        p2 = self.find(v2)
        if p1 != p2:
            self.sizes[p1] += self.sizes[p2]
            self.cnt -= self.sizes[p2]
            self.data[p2] = p1
    def same(self, v1: int, v2: int):
        return self.find(v1) == self.find(v2)
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        uf = UnionFind(n)
        res = None
        for n1, n2 in edges:
            if uf.find(n1 - 1) != uf.find(n2 - 1):
                uf.uni(n1 - 1, n2 - 1)
            else:
                res = [n1, n2]
        return res