Evolving Graph Components Count

Problem

Track the number of connected components as edges arrive over time.

timeline is a list of snapshots, each a list of undirected [u, v] edges. After adding each snapshot cumulatively, return the component count for that point in time; the number of nodes is one plus the largest node index seen anywhere.

Hint

Union-find handles incremental edge additions in near constant time each.

Test cases

case 1

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

expected: [3,2,1]

case 2

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

expected: [3,2,1]

case 3

in: [[[[0,1]],[[0,1]]]]

expected: [1,1]

Starter codePython

def evolving_components(timeline):
    # Your code here
    pass

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