Connected Components and Union-Find

DFS flood fill or a disjoint-set union

Counting islands or friend circles means counting connected components: start a DFS or BFS from each unvisited node and mark everything reachable. Union-find (disjoint set union) keeps a parent pointer per node, merges sets with union and finds representatives with find; with path compression it is nearly O(1) per operation. It shines when edges arrive one at a time and detects cycles in undirected graphs (a union of already-connected nodes).

Islands with DFS and cycle detection with union-find, run

I ran this with Python 3.12.3 (standard library only). The grid has 3 islands; the fourth edge (2, 0) connects nodes already in one set, revealing a cycle; 5 nodes form 2 components.

# Counting islands with DFS, and the same idea with union-find
def count_islands(grid):
    grid = [list(row) for row in grid]
    rows, cols, count = len(grid), len(grid[0]), 0
    def sink(r, c):
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1":
                grid[r][c] = "0"
                stack.extend([(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)])
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.parent[ra] = rb
        return True

print(count_islands(["11000", "11000", "00100", "00011"]))
d = DSU(5)
edges = [(0, 1), (1, 2), (3, 4), (2, 0)]
print([d.union(a, b) for a, b in edges])     # False: edge (2,0) closes a cycle
print("components:", len({d.find(i) for i in range(5)}))

Output:

3
[True, True, True, False]
components: 2

Use an explicit stack for big grids

Recursive DFS can hit Python's recursion limit on large grids; an explicit stack avoids it.

त्वरित जाँच: What does a failed union (both nodes already share a root) indicate in an undirected graph?

• The nodes are disconnected
• The graph is empty
• The edge would create a cycle
• The algorithm has a bug