685.冗余连接II

链接：685.冗余连接II
难度：Hard
标签：深度优先搜索、广度优先搜索、并查集、图
简介：在本问题中，有根树指满足以下条件的有向图。返回一条能删除的边，使得剩下的图是有 N 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

题解 1 - typescript

• 编辑时间：2020-09-17
• 执行用时：92ms
• 内存消耗：41.9MB
• 编程语言：typescript
• 解法介绍：[参考连接](https://leetcode-cn.com/problems/redundant-connection-ii/solution/rong-yu-lian-jie-ii-by-leetcode-solution/)。

class UnionFind {
  ancestor: number[];
  constructor(n: number) {
    this.ancestor = new Array(n).fill(0).map((_, i) => i);
  }
  find(index: number): number {
    return index === this.ancestor[index]
      ? index
      : (this.ancestor[index] = this.find(this.ancestor[index]));
  }
  union(u: number, v: number): void {
    this.ancestor[this.find(u)] = this.find(v);
  }
}
function findRedundantDirectedConnection(edges: number[][]): number[] {
  const nodeCount = edges.length;
  const uf = new UnionFind(nodeCount + 1);
  const parent: number[] = new Array(nodeCount + 1).fill(0).map((_, i) => i);
  let conflict = -1;
  let cycle = -1;
  for (let i = 0; i < nodeCount; i++) {
    const [node1, node2] = edges[i];
    if (parent[node2] !== node2) {
      conflict = i;
    } else {
      parent[node2] = node1;
      if (uf.find(node1) === uf.find(node2)) {
        cycle = i;
      } else {
        uf.union(node1, node2);
      }
    }
  }
  if (conflict < 0) {
    return [edges[cycle][0], edges[cycle][1]];
  } else {
    const [edge1, edge2] = edges[conflict];
    return cycle >= 0 ? [parent[edge2], edge2] : [edge1, edge2];
  }
}