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

20040번: 사이클 게임

 

 

[풀이 과정]

문제랑 입력을 보고 union find로 사이클 여부를 구해주는 문제라는 걸 알 수 있었다. 지난주에 kruskal 하면서도 썼던거라 빠르게 파악할 수 있었다. 

 

1. 입력받으면서 싸이클 여부를 파악한다. 

 

2. find_Cycle 함수에서 각 점의 루트 노드 값을 구해주고, 그 값을 기반으로 사이클이 돌고 있는지 확인해준다.

두 점의 루트 노드 값이 같다면 사이클이 돌고 있는 것이다. 

 

사이클이 돌고 있지 않다면 값이 작은 쪽으로 루트 노드 값을 변경시킨다. 

 

3. 루트 노드 값을 찾아주는 함수 find_parent

종료 조건은 (n==node[n])으로 이 경우 본인이 루트 노드인 경우이다.

 

[코드]

#include<iostream>
#include<algorithm>

using namespace std;

int N, M;
int node[500002];


int find_parent(int n) {
	if (n==node[n]) return n;
	return node[n] = find_parent(node[n]);
}

int find_Cycle(int n1, int n2) {
	int rootN1 = find_parent(n1);
	int rootN2 = find_parent(n2); 
	
	if (rootN1 == rootN2) return 1;
	if (rootN1 < rootN2) node[rootN2] = rootN1;
	else node[rootN1] = rootN2;
	return 0;
}

int main(){
	cin >> N >> M;

	for (int i = 0; i < N; i++) node[i] = i;
	int ans = 0;

	for (int i = 0; i < M; i++) {
		int n1, n2;
		cin >> n1 >> n2;
		if (find_Cycle(n1, n2)) {
			ans = i + 1;
			break;
		}
	}
	cout << ans;
	return 0;

}

 

 

[++개인 보강]

값을 변경하는 부분에서 루트 값끼리 비교를 하고 변경해줘야 한다. 

여기서 계속 n1, n2로 하는데 ㅠ 그럼 안됨.. ㅠㅠ 

 

그런 경우에 1->2  3->4 1->4 2->3 이런 사이클을 하면 문제가 생김 ... 주의하도록....