[백준] 1717 집합의 표현

문제 출처: https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

union 데이터 구조를 이용하여 find, merge를 하여 답을 구할 수 있다. 

여기서 A집합과 B집합의 크기와 상관없이 항상 A집합이 루트가 되도록 merge하는 방법으로 코드를 짜면 시간 초과가 발생 한다. 두 집합 중 크기가 큰 집합이 루트가 되도록 병합을 하여 시간 복잡도를 줄일 수 있다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int arr[1000001];
int find(int a) {
	if (arr[a] < 0)return a;
	return find(arr[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;
	if (arr[a] < arr[b]) {
		arr[a] += arr[b];
		arr[b] = a;
	}
	else{
		arr[b] += arr[a];
		arr[a] = b;
	}
}

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

	fill(&arr[0], &arr[1000001], -1);
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int command, a, b;
		cin >> command >> a >> b;
		if (command == 0) {
			merge(a, b);
		}
		else {
			a = find(a);
			b = find(b);
			if (a == b) {
				cout << "yes" << '\n';
			}
			else {
				cout << "no" << '\n';
			}
		}
	}
	

}