Build a Union-FindStep 5 of 5

Counting components (friend circles)

12345

Step 5: Counting components (friend circles)

Track how many disjoint groups exist. Store components = n in the constructor and decrease it by one on every successful union (when two different roots merge). Implement count() to return it.

Then implement the application count_groups(n, pairs): build a DSU over n people, union every (a, b) friendship pair, and return count(), the number of friend circles. The same idea underlies network connectivity and Kruskal's MST.

Hints
Starter code
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra = self.find(a)
        rb = self.find(b)
        if ra == rb:
            return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def count(self):
        """Return the number of disjoint components currently in the structure."""
        # TODO: return the running component counter.
        pass


def count_groups(n, pairs):
    """Return the number of connected groups among n items after unioning every pair."""
    # TODO: build a DSU(n), union each (a, b) in pairs, then return dsu.count().
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges