1579.js

/** ------------------------------------------------------------------------------
 * 
 * 2023-04-30
 * 1579. Remove Max Number of Edges to Keep Graph Fully Traversable
 * https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/
 * 
 ------------------------------------------------------------------------------ */
function maxNumEdgesToRemove(n, edges) {
  const aliceSet = new DisjointSet(n);
  const bobSet = new DisjointSet(n);
  let commonEdges = 0;

  for (const [type, u, v] of edges) {
    if (type === 3) {
      if (aliceSet.union(u - 1, v - 1) && bobSet.union(u - 1, v - 1)) {
        commonEdges++;
      }
    }
  }

  let aliceEdges = 0;
  for (const [type, u, v] of edges) {
    if (type === 1) {
      if (aliceSet.union(u - 1, v - 1)) {
        aliceEdges++;
      }
    }
  }

  let bobEdges = 0;
  for (const [type, u, v] of edges) {
    if (type === 2) {
      if (bobSet.union(u - 1, v - 1)) {
        bobEdges++;
      }
    }
  }

  if (aliceSet.count !== 1 || bobSet.count !== 1) {
    return -1;
  }

  return edges.length - commonEdges - aliceEdges - bobEdges;
}

class DisjointSet {
  constructor(n) {
    this.count = n;
    this.parent = new Array(n);
    for (let i = 0; i < n; i++) {
      this.parent[i] = i;
    }
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) {
      return false;
    }
    this.parent[rootX] = rootY;
    this.count--;
    return true;
  }
}