Node.js) 백준 4803번: 트리

https://www.acmicpc.net/problem/4803

4803번: 트리

 

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

let edges;
let visited;
let tc = 1;
let i = 0;
while (i < input.length - 1) {
	const [N, M] = input[i].split(' ').map(Number);

	visited = Array(N).fill(false);
	edges = Array.from(Array(N), () => []);
	for (let m = 0; m < M; m++) {
		const [x, y] = input[i + m + 1].split(' ').map((x) => +x - 1);
		edges[x].push(y);
		edges[y].push(x);
	}

	let tree = 0;
	for (let i = 0; i < N; i++) {
		if (!visited[i]) {
			if (dfs(-1, i)) tree++;
		}
	}
	if (tree == 0) {
		console.log(`Case ${tc}: No trees.`);
	} else if (tree == 1) {
		console.log(`Case ${tc}: There is one tree.`);
	} else {
		console.log(`Case ${tc}: A forest of ${tree} trees.`);
	}
	tc++;
	i = i + M + 1;
}

function dfs(parent, now) {
	visited[now] = true;
	for (let i = 0; i < edges[now].length; i++) {
		const next = edges[now][i];
		if (parent == next) continue;
		if (visited[next]) return false; // 사이클
		else {
			if (!dfs(now, next)) return false; // 사이클
		}
	}
	return true;
}