알고리즘/BAEKJOON
BOJ 1717 : 집합의 표현
피로물든딸기
2021. 6. 10. 16:32
반응형
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;
}
반응형