[BOJ] 20040 - 사이클게임

[백준] 20040 - 사이클게임

사이클 발생을 탐색한다는 것에서 유니온 파인드를 떠올릴 수 있다. 두 지점을 잇는 선분이 생길 때 마다 두 지점을 union한다.

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int par[500005];

int find(int x) {
	if (par[x] == x) return x;
	return par[x] = find(par[x]);
}

void uni(int x, int y) {
	if (find(x) == find(y)) return;
	par[find(x)] = find(y);
	find(x);
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i < n; i++) {
		par[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (find(x) == find(y)) {
			printf("%d\n", i);
			return 0;
		}
		else uni(x, y);
	}
	printf("0\n");
	return 0;
}