Component Size Multiset

Problem

Return the sizes of all connected components in ascending order.

edges is an undirected edge list and isolated nodes count as components of size 1. Traverse every unvisited node, measure the reachable region, and collect its size. The output is the sorted multiset of those sizes.

Hint

Flood fill from each unvisited node, then sort the collected sizes.

Test cases

case 1

in: [4,[[0,1],[2,3]]]

expected: [2,2]

case 2

in: [5,[]]

expected: [1,1,1,1,1]

case 3

in: [3,[[0,1],[1,2]]]

expected: [3]

case 4

in: [6,[[0,1],[2,3],[4,5]]]

expected: [2,2,2]

Starter codePython

def component_sizes(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor