Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Number of Connected Components

LeetCode #323Medium
Union-Find · count = n, merge drops count

Given n nodes labeled 0..n-1 and a list of undirected edges, return the number of connected components in the graph.

Asked atAmazonGoogleMeta
step 1 / 8
undirected graph
0
1
2
3
4
parent[]
01234
01234
Union-Find
▸
1parent[i] ← i ;  count ← n          // each node its own component
2find(x): while parent[x] != x: x = parent[x]; return x
3for (a, b) in edges:
4    ra, rb ← find(a), find(b)
5    if ra != rb: parent[rb] = ra; count--   // merge two components
6    // else: same component → edge redundant, count unchanged
7return count                          // # connected components
state
  • n5
  • count5
  • parent[0,1,2,3,4]

line 1Number of Connected Components (LeetCode 323): given n nodes and a list of undirected edges, count how many connected groups the graph splits into. Union-Find starts by assuming every node is its own component: parent[i] = i and count = n = 5. Each edge that joins two DIFFERENT components fuses them and drops the count by one.