연결 요소의 개수

문제

언어

  • JavaScript

문제 풀이 step 1

  • 연결 요소의 개수를 구해야 합니다.
  • 모든 정점이 연결된 그래프는 연결 요소가 하나일 것입니다.
  • 하지만 모든 정점이 연결되지 않은 그래프는 연결 요소가 여러개일 것입니다.
  • 이 문제는 DFS 탐색과 BFS 탐색 두 방법 다 가능합니다.
  • 왜냐하면 두 탐색 모두 모든 정점을 1 번씩 방문하는 알고리즘이기 때문이겠죠.
  • 저희는 그저 모든 정점마다 DFS 탐색을 실시합니다. 단, 이미 방문했던 정점에 대해서는 탐색을 실시하지 않습니다.
  • 방문하지 않은 정점에 대해서 탐색을 실시할 때만 횟수를 세어주면 그것이 정답이 됩니다.

소스 코드 1

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

const dfs = (graph, from, visited, depth) => {
	visited[from] = true;

	for (let i = 0; i < graph[from].length; i++) {
		const to = graph[from][i];
		if (visited[to]) continue;

		visited[to] = true;
		dfs(graph, to, visited, depth + 1);
	}
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const graph = Array.from({length: n + 1}, () => []);
	for (let i = 1; i < m + 1; i++) {
		const [from, to] = input[i].split(" ").map(Number);

		graph[from].push(to);
		graph[to].push(from);
	}

	let count = 0;
	const visited = Array.from({length: n}, () => false);
	for (let i = 1; i < n + 1; i++) {
		if (visited[i]) continue;

		// 방문하지 않은 정점에 대해서만 횟수를 세어주고, DFS 탐색을 실시!!
		count++;
		dfs(graph, i, visited, 0);
	}

	return count;
};

console.log(solution(input));