Node.js) 백준 20040번: 사이클 게임

 

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

20040번: 사이클 게임

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')
	.map((v) => v.split(' ').map(Number));

const [N, M] = input[0];

const uf = new UF(N + 1);

for (let i = 1; i <= M; i++) {
	const [x, y] = input[i];
	const px = uf.find(x);
	const py = uf.find(y);
	if (px == py) {
		console.log(i);
		process.exit(0);
	} else {
		uf.union(x, y);
	}
}

console.log(0);