export function numeroDeIslasII(
  m: number,
  n: number,
  operations: number[][]
): any {

  const parent = new Array(m * n).fill(-1);

  const result: number[] = [];

  let islands = 0;

  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
  ];

  const index = (r: number, c: number) => r * n + c;

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

    return parent[x];
  }

  function union(a: number, b: number) {

    const rootA = find(a);
    const rootB = find(b);

    if (rootA !== rootB) {
      parent[rootA] = rootB;
      islands--;
    }
  }

  for (const [r, c] of operations) {

    const current = index(r, c);

    if (parent[current] !== -1) {
      result.push(islands);
      continue;
    }

    parent[current] = current;
    islands++;

    for (const [dr, dc] of dirs) {

      const nr = r + dr;
      const nc = c + dc;

      if (
        nr < 0 ||
        nc < 0 ||
        nr >= m ||
        nc >= n
      ) continue;

      const neighbor = index(nr, nc);

      if (parent[neighbor] !== -1) {
        union(current, neighbor);
      }
    }

    result.push(islands);
  }

  return JSON.stringify(result);
}