Province Sizes

There are n cities (0 .. n-1) and a list of direct roads between them. A province is a group of cities connected directly or indirectly. Return the size of each province, sorted ascending.

provinceSizes(n, roads)

Input format: n | roads, roads as a,b pairs. Output the sizes, sorted, space-separated.

Examples

n=5, roads (0,1)(1,2)(3,4)   // → [2, 3]
n=4, no roads                // → [1, 1, 1, 1]
n=3, roads (0,1)(1,2)(0,2)   // → [3]

Walkthrough

Thinking it through

A province is a connected component of the road network — cities linked directly or through a chain of roads. You need to identify these clusters and count each one's size. Union-find fits naturally: merge cities connected by roads, then tally sizes from the resulting groups.

Why union-find over an explicit graph traversal

You could build an adjacency structure and run BFS/DFS from every unvisited city, counting component sizes. That works, but union-find offers simpler bookkeeping: instead of walking edges city by city, just repeatedly merge each road's two endpoints, letting the structure track connectivity as a byproduct.

Building the approach

Initialize every city as its own root.
For every road, union its two endpoints: find each root, link them if different. Connectivity is transitive — road A-B and later B-C eventually resolve A, B, and C to the same root.
Walk all n cities, find each one's root, and tally how many map to each distinct root in a counting map — each distinct root is one province, its tally the province's size.
Collect the tallies and sort ascending.

Why this correctly captures connectivity

"Same root" is exactly equivalent to "connected by some path of roads," including multi-hop connections — path compression keeps root lookups fast even as merge chains pile up. A city with zero roads still contributes as its own province of size 1, since it stayed its own root — no special-case logic needed.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.