BOJ 1717 : 집합의 표현

알고리즘 문제 전체 링크

 

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

 

 

유니온 파인드를 이용하여 문제를 풀 수 있다.

 

각 원소들의 부모를 자기 자신으로 초기화하고 입력을 받으면서 집합을 만든다.

find를 이용하여 같은 집합에 포함되어 있는지 체크하면 된다.

#include <stdio.h>

int N, M;
int parent[1000100]; 
			
int find(int x)
{
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]); // 경로 압축
}

void makeUnion(int x, int y)
{
	x = find(x);
	y = find(y);

	if (x != y) parent[x] = y;
}

int main(void)
{
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++) parent[i] = i;

	for (int i = 0; i < M;i++)
	{
		int tmp, a, b;

		scanf("%d %d %d", &tmp, &a, &b);

		if (tmp == 0) makeUnion(a, b);
		else
		{
			if (find(a) == find(b)) printf("YES\n");
			else printf("NO\n");
		}
	}

	return 0;
}