Medium

Number of Connected Components in an Undirected Graph

LAB

Given n nodes and undirected edges, return the number of connected components.

EXAMPLES

Example 1

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

Output
2

FUNCTION SHAPE

n: intedges: intMatrix→int

SOLUTION NOTE

This is actually a really important concept to know. Connected component is basically like an island.

Reveal reference solution +

pythonREFERENCE

def countComponents(self, n: int, edges: List[List[int]]) -> int:
    adjList = defaultdict(list)
    for u,v in edges:
        adjList[u].append(v)
        adjList[v].append(u)
    visited = set()
    ccs = []

    def dfs(i, cc):
        if i in visited: return
        visited.add(i)
        cc.append(i)
        for nbr in adjList[i]:
            dfs(nbr, cc)

    for i in range(n):
        if i in visited: continue
        cc = []
        dfs(i, cc)
        ccs.append(cc)

    return len(ccs)

TimeO(n+m)

SpaceO(n+m)

Open on LeetCode ↗