Node.js) 백준 24391번: 귀찮은 해강이

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

24391번: 귀찮은 해강이

 

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 readline = require('readline').createInterface({
	input: process.stdin,
	output: process.stdout,
});
let answer = 0;
let N = null;
let M = null;
let uf = null;
readline.on('line', (line) => {
	const input = line.split(' ').map(Number);
	if (uf == null) {
		[N, M] = input;
		uf = new UF(N + 1);
	} else if (M > 0) {
		const [a, b] = input;
		uf.union(a, b);
		M--;
	} else {
		const timeTable = input;
		for (let i = 1; i < timeTable.length; i++) {
			const prev = timeTable[i - 1];
			const now = timeTable[i];
			if (uf.find(prev) != uf.find(now)) {
				answer++;
			}
		}
	}
}).on('close', () => {
	console.log(answer);
	process.exit();
});