DuelCoder
Sign inPlay free
Blind 75 · #47 · Graphs

Number of Connected Components

MediumUnion-find or DFSTime O(V + E)Space O(V)

Number of Connected Components is a medium Graphs problem from the Blind 75. The key pattern is union-find or dfs, and a good solution runs in O(V + E) time.

Problem

Count connected components in an undirected graph with n labeled vertices.

Examples

Example 1

Input

{"n":6,"edges":[[0,1],[1,2],[3,4]]}

Output

3

Example 2

Input

{"n":5,"edges":[[0,4],[4,2],[1,3]]}

Output

2

Example 3

Input

{"n":5,"edges":[[0,1],[1,2],[2,3],[3,4]]}

Output

1

Approach

Start with n components and merge them edge by edge, or count how many traversals it takes to visit every vertex.

PatternUnion-find or DFS
TimeO(V + E)
SpaceO(V)

Watch out for

Vertices with no edges are components too.

More Graphs problems