백준 1717 집합의 표현 (c++) : 피너클

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

1717번: 집합의 표현

유니온 파인드 문제다.

int n, m;
int parent[1000001];

사용할 변수다.

parent[5] = 10이라면 5의 조상이 10이라는 의미다.

parent[i] = j이라면 i의 조상이 j이라는 의미다.

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

find함수다. u의 조상을 반환한다.

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	parent[u] = v;
}

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

cin >> n >> m;
for (int i = 1; i <= n; i++) parent[i] = i;

메인함수에서 n과 m을 입력받은뒤 parent를 초기화한다.

for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;

    if (a == 0) merge(b, c);
    else {
        if (find(b) == find(c)) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}

그후 m만큼 a, b, c를 입력받는다.

a == 0이라면 b와 c를 합친다.

a == 1이라면 b의 조상과 c의 조상이 같다면 YES를 출력하고 아니면 NO를 출력한다.

#include <iostream>

using namespace std;

int n, m;
int parent[1000001];

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	parent[u] = v;
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) parent[i] = i;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		if (a == 0) merge(b, c);
		else {
			if (find(b) == find(c)) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}
}