Node.js) 백준 1976번: 여행 가자

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

 

class Edge {
	constructor() {
		this.src = 0;
		this.dest = 0;
	}
}

class SubSet {
	constructor(i) {
		this.parent = i;
		this.rank = 0;
	}
}

class UF {
	constructor(N) {
		this.subsets = Array.from(Array(N), (_, i) => {
			return new SubSet(i);
		});
	}

	find(i) {
		if (this.subsets[i].parent == i) {
			return i;
		} else {
			this.subsets[i].parent = this.find(this.subsets[i].parent);
			return this.subsets[i].parent;
		}
	}

	union(x, y) {
		const xroot = this.find(x);
		const yroot = this.find(y);
		if (this.subsets[xroot].rank < this.subsets[yroot].rank) {
			this.subsets[xroot].parent = yroot;
		} else if (this.subsets[xroot].rank > this.subsets[yroot].rank) {
			this.subsets[yroot].parent = xroot;
		} else {
			this.subsets[xroot].parent = yroot;
			this.subsets[yroot].rank++;
		}
	}
}

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const M = +input.shift();
const R = input
	.pop()
	.split(' ')
	.map((v) => +v - 1);
const E = input.map((v) => v.split(' ').map(Number));
const uf = new UF(N);

E.forEach((src, x) => {
	src.forEach((dest, y) => {
		if (dest == 1) {
			uf.union(x, y);
		}
	});
});

let possible = 'YES';
let p = uf.find(R[0]);

for (let i = 1; i < R.length; i++) {
	const now = R[i];
	if (uf.find(now) != p) {
		possible = 'NO';
		break;
	}
}

console.log(possible);