백준 20040번 사이클 게임 C++ 유니온 파인드, 분리 집합

리뷰

노드 간 간선이 주어질때 사이클이 존재하는지 체크하고 사이클이 존재한다면 해당 간선의 입력 순서를 출력하는 문제

 

문제 풀이

1. 노드의 개수는 최대 50만 이므로 50만 1짜리 정수형 배열을 선언해 준다.
2. n과 m값을 입력 받고 n개의 노드를 인덱스를 1부터, 자기 자신의 인덱스를 value로 갖게끔 초기화 해준다.
3. m번의 간선 정보를 입력 받고, 만약 a와 b가 같은 그룹에 속해 있다면 현재 간선이 입력된 번째를 출력하고 return
4. 같은 그룹에 속해있지 않다면 a와 b를 Union 처리 해준다.
5. 간선 정보를 모두 입력받아도 return되지 않았다면 0을 출력해 준다.

 

참고 사항

같은 그룹에 속해 있다는 것은 두 노드를 Find해주고 반환된 값이 서로 같은 경우이다.

 

 

정답 코드

#include<iostream>

using namespace std;

int n, m;
int nodes[500001];

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int rootA = Find(a);
	int rootB = Find(b);
	if (rootA == rootB) return;
	nodes[rootB] = rootA;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) nodes[i] = i;
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b;
		if (Find(a) == Find(b)) {
			cout << i;
			return 0;
		}
		Union(a, b);
	}
	cout << 0;
	return 0;
}