Components & Cycles

The Idea

Give every element its own group and set a counter to n. Then walk the edges.

A union that merges two different roots drops the counter by one. A union that finds one shared root changes nothing — and that edge is exactly a cycle, because both ends were already reachable from each other. One pass answers both questions.

Real-World Example

A crew laying fibre between buildings. Each new cable either connects two networks that were separate — progress — or links two buildings already on the same loop, which is spare capacity, not coverage. The counter says how many crews are still needed.

The Code

parent = list(range(6))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

edges = [(0, 1), (1, 2), (0, 2), (3, 4)]
components, cycles = 6, 0
for a, b in edges:
    ra, rb = find(a), find(b)
    if ra == rb: cycles += 1        # both ends already linked
    else: parent[ra], components = rb, components - 1
print(components, cycles)

parent = list(range(4))
def find(x):
  while parent[x] != x:
      x = parent[x]
  return x
count = 4
for a, b in [(0, 1), (2, 3), (1, 3)]:
  ra, rb = find(a), find(b)
  if ra != rb:
      parent[ra] = rb
      count -= 1
print(count)