2018-05-12-1.md

문제

• 백준 온라인저지 1717번 - 집합의 표현
• https://www.acmicpc.net/problem/1717

풀이

• 유니온 파인드를 이용하면 쉽게 구할 수 있다.

코드

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

using namespace std;

int parent[1000001];


int Find(int x){

	if(x == parent[x]){
		return x;
	}
	else{
		int p = Find(parent[x]);
		parent[x] = p;
		return p;
	}

}

void Union(int x, int y){

	x = Find(x);
	y = Find(y);

	parent[y] = x;

}

int main(){

	int n, m;

	scanf("%d %d", &n, &m);

	// 각자 자신의 부모를 자기 자신으로 초기화
	for(int i=0; i<n+1; i++){
		parent[i] = i;
	}

	int op, a, b;
	while(m--){
		scanf("%d %d %d", &op, &a, &b);

		if(op==0){

			Union(a,b);

		}
		else if(op==1){

			if(Find(a) == Find(b)){
				printf("YES\n");
			}

			else{
				printf("NO\n");
			}

		}

	}

	return 0;
}

반성

• printf와 scanf를 사용해야 시간초과가 나지 않았다.

기타

참고자료

• https://twpower.github.io/115-union-find-disjoint-set