백준 20040 사이클 게임 (c++) : 피너클

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

20040번: 사이클 게임

유니온 파인드를 이용한 문제다.

두 점을 입력받은뒤 둘의 부모가 같다면 순서를 출력한다.

int n, m;
int uni[500001];

사용할 변수들이다. uni가 점의 부모를 의미한다.

int find(int num) {
	if (uni[num] == num) return num;
	else return uni[num] = find(uni[num]);
}

find함수는 정수 num의 조상을 리턴한다.

uni[num]과 num이 같다면 num은 다른 정수의 조상이란 뜻이다.

void merge(int u, int v){
    u = find(u);
    v = find(v);
    uni[u] = v;
}

merge함수는 u와 v를 합친다.

서로의 조상을 찾은뒤 u의 부모를 v로 바꾼다.

cin >> n >> m;
for (int i = 0; i < n; i++) uni[i] = i;

이제 main에서 값을 입력받는다. 초기에 uni는 모두 자기 자신으로 초기화한다.

for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	if (find(a) == find(b)) {
		cout << i + 1 << endl;
		return 0;
	}
	merge(a, b);
}

이제 값들을 입력받으며 확인한다.

a와 b의 조상이 같다면 a와 b은 이미 연결되어있다는 뜻이다. 현재 순서를 출력한뒤 main함수를 종료시킨다.

아니라면 merge를 통해 a와 b를 서로 합친다.

cout << 0 << endl;

만약 모든 숫자를 입력받았는데도 연결된걸 찾지 못했다면 0을 출력한다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
vector<pair<int, int>> v;
vector<int> rnk(500001, 1);
int uni[500001];


int find(int num) {
	if (uni[num] == num) return num;
	else return uni[num] = find(uni[num]);
}

void merge(int u, int v){
    u = find(u);
    v = find(v);
    uni[u] = v;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) uni[i] = i;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		if (find(a) == find(b)) {
			cout << i + 1 << endl;
			return 0;
		}
		merge(a, b);
	}
	cout << 0 << endl;

}

전체코드다.