초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
NO
NO
YES
유니온 파인드 문제.
먼저 parent[]라는 배열을 선언한다. i번째 index에는 i의 1단계 위의 부모 원소의 번호가 들어있다.
merge 함수에서는 두 원소 a, b를 받아 그 원소가 들어있는 두 집합을 합친다. a, b 각각의 최상위 부모를 찾아서 둘 중 하나를 같게 만들면, 두 트리가 합쳐진다.
find_parent 함수는 원소 x의 최상위 부모를 찾아 반환한다. 만약 parent[x]와 x가 같다면, x가 최상위 원소이므로 x를 반환한다.
x가 최상위 원소가 아니라면, 최상위 원소를 찾을 때까지 재귀한다. 그 과정에서 찾아지는 모든 원소의 부모를 최상위 원소로 교체한다.
예를 들어, 아래와 같은 트리가 있다고 할 때
find_parent(5)를 수행하고 나면, 아래와 같은 모습으로 변한다.
이렇게 하면 다음 번에 최상위 노드를 찾을 때 여러 번 재귀하지 않아도 돼서 더 빠르다.
#include <iostream>
using namespace std;
int n, m;
int parent[1000001];
void set_io(void);
void input_data(void);
void union_find(void);
int find_parent(int child);
void merge(int a, int b);
void is_in_union(int a, int b);
int main(void)
{
set_io();
input_data();
union_find();
return (0);
}
void set_io(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return ;
}
void input_data(void)
{
cin >> n >> m;
int i = -1;
while (++i <= n)
parent[i] = i;
return ;
}
void union_find(void)
{
int calculation, a, b;
int i = -1;
while (++i < m)
{
cin >> calculation >> a >> b;
if (calculation == 0)
merge(a, b);
else if (calculation == 1)
is_in_union(a, b);
}
return ;
}
int find_parent(int x)
{
if (parent[x] == x)
return x;
parent[x] = find_parent(parent[x]);
return (parent[x]);
}
void merge(int a, int b)
{
a = find_parent(a);
b = find_parent(b);
if (a > b)
parent[a] = b;
else if (a < b)
parent[b] = a;
return ;
}
void is_in_union(int a, int b)
{
if (find_parent(a) == find_parent(b))
cout << "YES" << '\n';
else
cout << "NO" << '\n';
return ;
}
성공 ㅎ-ㅎ
요즘 넘 해이해진 것 같다.. 더 열심히 하자(진짜로)