素集合 (Union-Find) でケーブルでつながったパソコンの組を数える

def find(parent, x):
    top = x
    while parent[top] != top:
        top = parent[top]
    while parent[x] != top:
        up = parent[x]
        parent[x] = top
        x = up
    return top


def count_networks(n, cables):
    parent = list(range(n))
    size = [1] * n
    groups = n
    for a, b in cables:
        ra = find(parent, a)
        rb = find(parent, b)
        if ra == rb:
            continue
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
        groups -= 1
    return groups

function find(parent, x) {
  let top = x;
  while (parent[top] !== top) {
    top = parent[top];
  }
  while (parent[x] !== top) {
    const up = parent[x];
    parent[x] = top;
    x = up;
  }
  return top;
}

function countNetworks(n, cables) {
  const parent = [];
  const size = [];
  for (let i = 0; i < n; i++) {
    parent.push(i);
    size.push(1);
  }
  let groups = n;
  for (const [a, b] of cables) {
    let ra = find(parent, a);
    let rb = find(parent, b);
    if (ra === rb) {
      continue;
    }
    if (size[ra] < size[rb]) {
      [ra, rb] = [rb, ra];
    }
    parent[rb] = ra;
    size[ra] += size[rb];
    groups--;
  }
  return groups;
}

func find(
	parent []int, x int,
) int {
	top := x
	for parent[top] != top {
		top = parent[top]
	}
	for parent[x] != top {
		up := parent[x]
		parent[x] = top
		x = up
	}
	return top
}

func countNetworks(
	n int, cables [][]int,
) int {
	parent := make([]int, n)
	size := make([]int, n)
	for i := range parent {
		parent[i] = i
		size[i] = 1
	}
	groups := n
	for _, c := range cables {
		ra := find(parent, c[0])
		rb := find(parent, c[1])
		if ra == rb {
			continue
		}
		if size[ra] < size[rb] {
			ra, rb = rb, ra
		}
		parent[rb] = ra
		size[ra] += size[rb]
		groups--
	}
	return groups
}