Problem 558023 · medium · Phase 05 Advanced Algorithms & Graphs

Sizes of Every Component

graphs · BFS · connected components

An undirected graph with nodes 0 .. n-1 is given as n and an edge list edges. Two nodes are in the same component when a path connects them. Return the sizes (number of nodes) of all components, sorted from largest to smallest. Isolated nodes are components of size 1.

Examples

Input:  n = 7, edges = [[0,1],[1,2],[3,4]]
Output: [3, 2, 1, 1]
Explanation: {0,1,2}, {3,4}, {5}, {6}.

Input:  n = 3, edges = []
Output: [1, 1, 1]

Constraints

  • 1 <= n <= 2 * 10**4, 0 <= len(edges) <= 5 * 10**4
  • Edges may repeat. Target O(V + E + c log c) time where c is the number of components.

Goals

  • Run a search from each unvisited node and measure what it reaches
  • Return a summary of components rather than just their count
Starting Python…