문제
https://www.acmicpc.net/problem/1717
문제해설
첫째줄에 숫자의 갯수 n과 m개의 연산 갯수가 주어진다.
연산은 0 a b 형태이면 a와 b를 합친다는 것이고
1 a b 형태이면 a와 b가 같은 집합인지 판별하라는 것이다.
문제풀이
기본적인 유니온파인드 문제이다.
0이면 유니온 연산을 해주면되고
1이면 파인드를 이용해 같은 집합인지 판별하면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
using namespace std;
int parent[1000001];
int find(int x) {
if (parent[x] == x)
return x;
parent[x] = find(parent[x]);
return parent[x];
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
parent[y] = x;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i < 1000001; i++)
parent[i] = i;
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &c, &a, &b);
if (c == 0) {
merge(a, b);
}
else {
if (find(a) == find(b))
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}