[백준] 11724번 / 실버2 / 연결 요소의 개수 / Node.js

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력

2

소스 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => v.split(' ').map(Number));

function solution(input) {
  const [N, M] = input[0];
  const graph = new Array(N + 1).fill(0).map(el => new Array(N + 1).fill(0));
  const visited = new Array(N + 1).fill(false);
  let count = 0;

  for (let i = 1; i < input.length; i++) {
    const [y, x] = input[i];
    graph[y][x] = 1;
    graph[x][y] = 1;
  }

  const dfs = (num) => {
    if (visited[num]) return;
    visited[num] = true;

    for (let i = 0; i < graph[num].length; i++) {
      if (graph[num][i] === 1 && !visited[i]) {
        dfs(i);
      }
    }
  }

  for (let i = 1; i <= N; i++) {
    if (!visited[i]) {
      count++;
      dfs(i);
    }
  }

  console.log(count);
  return;
}

solution(input);