Node.js) 백준 1043번: 거짓말

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

1043번: 거짓말

 

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, M] = input.shift();

const trueman = new Set(input.shift().slice(1));

const party = input.map((v) => v.slice(1));

const edges = Array(N + 1)
	.fill(null)
	.reduce((r, v, i) => {
		r[i] = [];
		return r;
	}, {});

party.forEach((arr) => {
	for (let i = 0; i < arr.length; i++) {
		for (let j = i + 1; j < arr.length; j++) {
			if (!edges[arr[i]].includes(arr[j])) {
				edges[arr[i]].push(arr[j]);
			}

			if (!edges[arr[j]].includes(arr[i])) {
				edges[arr[j]].push(arr[i]);
			}
		}
	}
});

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

const answer = party
	.map((arr) => {
		const start = arr[0];
		visited = visited.map((v) => false);
		visited[start] = true;
		return knowTrue(start);
	})
	.filter((v) => !v).length;

console.log(answer);

function knowTrue(man) {
	if (trueman.has(man)) return true;
	const friends = edges[man];

	for (let i = 0; i < friends.length; i++) {
		const friend = friends[i];
		if (trueman.has(friend)) return true;
		else {
			if (!visited[friend]) {
				visited[friend] = true;
				if (knowTrue(friend)) return true;
				visited[friend] = false;
			}
		}
	}
	return false;
}