https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a
www.acmicpc.net
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
//집합의 표현 1717번
vector<int> v; //(본인정보, 부모정보)
int my_find(int me)
{
if(me == v[me])
{
return me;
}
return v[me] = my_find(v[me]);
}
void my_union(int a, int b)
{
int A = my_find(a);
int B = my_find(b);
if(A == B)
{
return;
}
v[A] = B;
}
int main(void)
{
int n,m;
int q, from, to;
scanf("%d %d", &n, &m);
v.push_back(0);
for(int i=1; i<=n; i++)
{
v.push_back(i);
}
for(int i=0; i<m; i++)
{
scanf("%d %d %d", &q, &from, &to);
if(q == 0)
{
my_union(from, to);
}
else if(q==1)
{
if(my_find(from) == my_find(to))
{
printf("YES \n");
}
else
{
printf("NO \n");
}
}
}
return 0;
}