Connected Components

The Idea

A graph need not be one piece. Run a traversal from a node and you reach exactly its component — nothing more. So loop over every node, and each time you meet one nobody has visited, start a fresh sweep and add one to the count.

Real-World Example

A coin-counting machine photographs the tray and looks at touching pixels. Each blob of connected bright pixels is one coin; a gap of background pixels between two blobs means two coins. The count of separate blobs is a count of components, and it needs no idea of what a coin looks like.

The Code

pixels = {1: [2], 2: [1], 3: [4, 5], 4: [3], 5: [3], 6: []}

def flood(p, seen, blob):
    seen.add(p)
    blob.append(p)
    for q in pixels[p]:              # spread to touching pixels
        if q not in seen:
            flood(q, seen, blob)
    return blob

seen, blobs = set(), []
for p in pixels:
    if p not in seen:                # a region nobody has reached
        blobs.append(flood(p, seen, []))
print(len(blobs), blobs)   # 3 [[1, 2], [3, 4, 5], [6]]

g = {1: [2], 2: [1], 3: []}
seen, count = set(), 0
for n in g:
  if n ___ seen:
      count += 1
      seen.update([n] + g[n])
print(count)   # 2