C++[백준]20040번 사이클 게임

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

20040번: 사이클 게임

 

솔루션

---

처음에.. 모든 노드를 다 둘러서 다시 시작점으로 와야 하는 줄 알고 착각하고.. 문제 어렵다 생각했는데,

 

문제를 다시 보니, 특정 점에서 얼만큼 방문하던, 다시 특정 점으로 오면 된다고 한다. (이래서 글을 유심히 읽어야 한다.)

 

 

그래서 생각을 해 낸 것이,

UnionFind이다.

 

 각각의 선분을 그을 때, 이를 하나의 집합으로 연결 시킨다.

 이 때, 선분을 그었는데, 이미 같은 집합이라면, 사이클이 반드시 생기는데, 몇번째에 같은 집합을 합치는 지 출력을 하면 된다.

 

 

 

코드

---

#include <iostream>
using namespace std;

int parent[500002];
int N, M;

int getParent(int x) {
	if (x == parent[x]) return x;
	else return parent[x] = getParent(parent[x]);
}

bool IsUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	return a == b;
}

void SetUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	
	a > b ? parent[b] = a : parent[a] = b;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> M;
	for (int i = 0; i < N; i++) parent[i] = i;
	
	for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b;
		if (!IsUnion(a, b)) {
			SetUnion(a, b);
		}
		else {
			cout << i << "\n";
			return 0;
		}
	}
	
	cout << "0\n";
	return 0;
}