← 15주차 · 그래프와 DFS · BFS
보통그래프DFSBFS

연결 요소의 개수

정점 개수 n과 간선 목록 edges로 이루어진 무방향 그래프가 주어져요. 정점은 0번부터 n-1번까지 있어요.

서로 이어져 한 덩어리를 이루는 정점 묶음을 연결 요소라고 해요. 이 그래프에 연결 요소가 몇 개인지 반환해요.

한 정점에서 시작한 탐색은 그 덩어리 하나만 훑어요. 그래서 모든 정점을 돌면서 아직 방문하지 않은 정점을 만날 때마다 거기서 새 탐색을 시작하고, 시작한 횟수가 곧 연결 요소의 개수예요.

예시

예시 1
입력
n = 5, edges = [[0, 1], [1, 2], [3, 4]]
출력
2
설명
{0, 1, 2}와 {3, 4} 두 덩어리예요.
예시 2
입력
n = 4, edges = []
출력
4
설명
간선이 없어 정점 하나하나가 각자 덩어리예요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ edges.length ≤ 200,000
  • 0 ≤ a, b < n
인접 리스트와 방문 배열을 만들어요. 0번부터 n-1번까지 보면서 아직 방문하지 않은 정점이면 개수를 1 늘리고, 그 정점에서 DFS나 BFS로 같은 덩어리를 모두 방문 표시해요.
javascript
function countComponents(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  const visited = new Array(n).fill(false);
  let count = 0;
  for (let i = 0; i < n; i++) {
    if (visited[i]) continue;
    count++;
    const stack = [i];
    visited[i] = true;
    while (stack.length > 0) {
      const v = stack.pop();
      for (const next of graph[v]) {
        if (!visited[next]) {
          visited[next] = true;
          stack.push(next);
        }
      }
    }
  }
  return count;
}
이전 문제경로 존재 판별
다음 문제섬의 개수
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.