0924-minimize-malware-spread.js

/**
 * 924. Minimize Malware Spread
 * https://leetcode.com/problems/minimize-malware-spread/
 * Difficulty: Hard
 *
 * You are given a network of n nodes represented as an n x n adjacency matrix graph, where the ith
 * node is directly connected to the jth node if graph[i][j] == 1.
 *
 * Some nodes initial are initially infected by malware. Whenever two nodes are directly connected,
 * and at least one of those two nodes is infected by malware, both nodes will be infected b
 * malware. This spread of malware will continue until no more nodes can be infected in this manner.
 *
 * Suppose M(initial) is the final number of nodes infected with malware in the entire network after
 * the spread of malware stops. We will remove exactly one node from initial.
 *
 * Return the node that, if removed, would minimize M(initial). If multiple nodes could be removed
 * to minimize M(initial), return such a node with the smallest index.
 *
 * Note that if a node was removed from the initial list of infected nodes, it might still be
 * infected later due to the malware spread.
 */

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function(graph, initial) {
  const n = graph.length;
  const parent = new Array(n).fill().map((_, i) => i);
  const size = new Array(n).fill(1);

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (graph[i][j] === 1) {
        union(i, j);
      }
    }
  }

  let maxSize = 0;
  let result = Math.min(...initial);

  for (const node of initial) {
    const root = find(node);
    let componentInfected = 0;

    for (const infectedNode of initial) {
      if (find(infectedNode) === root) {
        componentInfected++;
      }
    }

    if (componentInfected === 1 && size[root] > maxSize) {
      maxSize = size[root];
      result = node;
    } else if (componentInfected === 1 && size[root] === maxSize) {
      result = Math.min(result, node);
    }
  }

  return result;

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

  function union(x, y) {
    const rootX = find(x);
    const rootY = find(y);
    if (rootX !== rootY) {
      parent[rootX] = rootY;
      size[rootY] += size[rootX];
    }
  }
};