1579.保证图可完全遍历

链接：1579.保证图可完全遍历
难度：Hard
标签：并查集、图
简介：给你一个数组 edges ，其中 edges[i] = [typei, ui, vi]  表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice 和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。

题解 1 - typescript

• 编辑时间：2021-01-27
• 执行用时：312ms
• 内存消耗：70.6MB
• 编程语言：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 maxNumEdgesToRemove(n: number, edges: number[][]): number {
  let ans = 0;
  const uf1 = new UnionFind(n);
  const uf2 = new UnionFind(n);
  edges.sort(([type1], [type2]) => (type1 === 3 ? -1 : 0));
  for (let [type, u, v] of edges) {
    u--;
    v--;
    if (type === 1) {
      if (uf1.same(u, v)) ans++;
      else uf1.union(u, v);
    } else if (type === 2) {
      if (uf2.same(u, v)) ans++;
      else uf2.union(u, v);
    } else {
      if (uf1.same(u, v) && uf2.same(u, v)) ans++;
      uf1.union(u, v);
      uf2.union(u, v);
    }
  }
  if (uf1.size !== 1 || uf2.size !== 1) return -1;
  return ans;
}