Implement Kruskal's and Prim's MSTStep 5 of 5

Connectivity via the MST

12345

Step 5: Connectivity via the MST

A spanning tree over n nodes has exactly n-1 edges. If Kruskal's algorithm cannot collect n-1 edges, the graph is split into more than one component and cannot be fully connected. This gives a clean connectivity test built directly on the work you have already done.

Implement is_connected(n, edges):

  • Reuse kruskal_edges from Step 3.
  • Return True if the chosen edges number exactly n-1 (the graph spans all n nodes), otherwise False.

Real use: before committing to a cabling plan, confirm the design actually reaches every site, no stranded, unconnected locations.

Hints
Starter code
import heapq


class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

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


def kruskal(n, edges):
    dsu = DSU(n)
    total = 0
    for w, u, v in sorted((w, u, v) for (u, v, w) in edges):
        if dsu.union(u, v):
            total += w
    return total


def kruskal_edges(n, edges):
    dsu = DSU(n)
    chosen = []
    for w, u, v in sorted((w, u, v) for (u, v, w) in edges):
        if dsu.union(u, v):
            chosen.append((u, v, w))
    return chosen


def prim(n, adj):
    visited = [False] * n
    heap = [(0, 0)]
    total = 0
    count = 0
    while heap and count < n:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        count += 1
        for v, wt in adj.get(u, []):
            if not visited[v]:
                heapq.heappush(heap, (wt, v))
    return total


def is_connected(n, edges):
    """Return True if the MST spans all n nodes (chosen edges == n-1), else False."""
    # TODO: build the MST edges and compare their count to n-1
    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