백준 1717번 : 집합의 표현 - Union&Find algorithm

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

1717번: 집합의 표현

#include <stdio.h>
#include <iostream>

using namespace std;

int unf[1000002];
int Find(int v){
	if(v==unf[v]) return v;
	else{
		return unf[v]=Find(unf[v]);
	}
}

void Union(int a, int b){
	a = Find(a);
	b = Find(b);
	if(a!=b){
		unf[a] = b;
	}
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i,n, m,a,b,c;
	scanf("%d %d",&n,&m);
	
	for(i=1; i<=n; i++){
		unf[i] = i;
	}
	
	
	for(i=0; i<m; i++){
		scanf("%d %d %d", &a,&b,&c);
		if(a==1){
			int v1 = Find(b);
			int v2 = Find(c);
			if(v1==v2) printf("YES\n");
			else printf("NO\n");
		}
		else{
			int v1 = Find(b);
			int v2 = Find(c);
			if(v1!=v2){
				Union(b,c);
			}
		}
	}
	
}

집합을 나타내는 방법을

 

union & find 알고리즘을 이용하여 풀 수 있다.