문제 링크

---

- 풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("
");

const [N, M] = input[0].split(" ").map(Number);

let graph = Array.from({ length: N + 1 }, () => []);

let visited = Array(N + 1).fill(false);

let answer = 0;

for (let i = 1; i <= M; i++) {
  const [x, y] = input[i].split(" ").map(Number);

  graph[x].push(y);
  graph[y].push(x);
}

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

function dfs(vertex) {
  if (visited[vertex]) {
    return;
  }

  visited[vertex] = true;

  for (let x of graph[vertex]) {
    if (!visited[x]) {
      dfs(x);
    }
  }
}

console.log(answer);

여기서 연결 요소의 개수라는 것은, 각각 노드들이 연결 되어있는 집합의 개수를 의미한다.

예를 들어서 1 -2 -3 번 노드가 연결이 되어있고, 4-5, 그리고 6이 각각 연결 되어있다면 연결요소으, 개수는 3개가 된다.

1번 노드부터 반복문으로 차례대로 돌면서 dfs 함수를 통해 연결되어있는 부분들을 탐색해준다.

또 shift() 함수를 통해 배열에서 값을 추출해주었었는데, 이러면 시간 초과가 난다.

아예 인덱스 값을 직접 지정해주는식으로 문제를 풀어야 할것 같다.