문제링크
https://www.acmicpc.net/problem/1717
조건
- 시간 제한 : 2s
- 메모리 제한 : 128MB
문제
초기에 {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 를 출력해도 된다)
해설
유니온-파인드 알고리즘을 이용하면 쉽게 해결할 수 있는 문제. 애초에 유니온 파인드를 연습하기 위해 출제된 문제이다!
문제에서 주어진 0 연산 (합집합 연산) 은 유니온-파인드 알고리즘에서 unite 연산에 해당하고, 1 연산(두 원소가 같은 집합에 포함되었는지 확인하는 연산)은 find 연산으로 구한 두 최상위 부모 노드를 비교하는 연산에 해당한다.
풀이
union_find 구조를 작성해주어 쉽게 해결이 가능하다.
합집한 연산(unite)은 두 원소가 포함된 그룹을 합치는 함수를 이용해 해결할 수 있다. find 연산으로 구한 두 최상위 부모 노드가 같은지를 비교하는 함수인 isSameSet 함수를 새로 만들어 1 연산에서 사용해주었다.
이 문제를 단순한 find 함수로 해결하기에는 시간이 부족하여, 모든 노드를 최상위 부모 노드로 연결하는 경로 단축 find 함수를 작성해주어 시간을 절약하였다.
struct union_find {
int parent[SIZE];
int size[SIZE] = {0,};
union_find(int n) {
for(int i = 0; i <= n; i++) {
parent[i] = i;
}
}
int find(int node) {
if(node == parent[node]) return node;
int temp = find(parent[node]);
parent[node] = temp;
return temp;
}
void unite(int A, int B) {
A = find(A);
B = find(B);
if(size[A] < size[B]) swap(A, B);
parent[B] = A;
size[A] += size[B];
}
bool isSameSet(int A, int B) {
return find(A) == find(B);
}
};
코멘트
값의 범위를 잘 보자! node 의 개수는 n개가 아니라, node의 번호가 0~n 까지였다!
코드
#include <iostream>
const int SIZE = 1000001;
using namespace std;
struct union_find {
int parent[SIZE];
int size[SIZE] = {0,};
union_find(int n) {
for(int i = 0; i <= n; i++) {
parent[i] = i;
}
}
int find(int node) {
if(node == parent[node]) return node;
int temp = find(parent[node]);
parent[node] = temp;
return temp;
}
void unite(int A, int B) {
A = find(A);
B = find(B);
if(size[A] < size[B]) swap(A, B);
parent[B] = A;
size[A] += size[B];
}
bool isSameSet(int A, int B) {
return find(A) == find(B);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
union_find UF = union_find(n);
while(m--) {
int type, a, b;
cin >> type >> a >> b;
if(!type) UF.unite(a, b);
else {
cout << ((UF.isSameSet(a, b))? "YES\n":"NO\n");
}
}
return 0;
}
Uploaded by Notion2Tistory v1.1.0