[백준 1717] 집합의 표현_union-find(c++)

[문제]

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

1717번: 집합의 표현

 

[문제풀이]

• n개의 수와 m개의 연산을 입력으로 받는다
• m개의 줄에는 각각의 연산이 주어지는에 첫번째 숫자가 0 이면 union연산을
• 첫번째 숫자가 1이면 find연산을 하면된다
• find연산을 할때, 두개의 숫자가 같은 부모노드를 가지고 있다면 YES를
• 아니라면 NO를 출력하면 된다

 

[전체코드]

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

vector<int> parent;
vector<int> rankk;

int find(int node){
	if(node == parent[node]) return node;
	else {
		int other = find(parent[node]);
		parent[node] = other;
	}
	return parent[node];
}

void union_xy(int xnode, int ynode){
	int x = find(xnode);
	int y = find(ynode);
	
	if(x == y) return;
	
	if(rankk[x] < rankk[y]) parent[x] = y;
	else parent[y] = x;
	
	if(rankk[x] == rankk[y]) rankk[x]++;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	parent = vector<int> (n+1,0);	
	rankk = vector<int> (n+1,0);
	
	for(int i = 0; i <= n; i++) parent[i] = i;//부모노드 자기자신으로 셋팅
	
	while(m--){
		int whatt, a, b;
		cin >> whatt >> a >> b;
		
		if(whatt == 0){
			union_xy(a,b);
		}else {
			int af = find(a);
			int bf = find(b);
			
			if(af == bf) cout << "YES\n";
			else cout << "NO\n";
		}
	}
	
	return 0;
}