PS/BOJ
[자료구조] 백준 1717번: 집합의 표현 (C++)
도비(Doby)
2022. 3. 6. 19:58
https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
분리 집합(Disjoint Set)은 Union-Find기법으로 처리할 수 있다.
union: 집합을 합침
find:어떤 두 원소가 하나의 집합에 속해있는지 확인
허나, 이 Union-Find는 이미 Kruskal's Algorithm을 공부하면서 알게 되었었다.
https://draw-code-boy.tistory.com/197
[알고리즘] 최소 스패닝 트리 (C++), 크루스칼 알고리즘
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내..
draw-code-boy.tistory.com
[AC 코드]
#include <iostream>
#include <vector>
#define MAX_V (1000000 + 1)
using namespace std;
int n, m;
int root[MAX_V];
int getRoot(int node){
if(root[node] == node) return node;
return root[node] = getRoot(root[node]);
}
void unionNode(int a, int b){
int rootA = getRoot(a);
int rootB = getRoot(b);
if(rootA > rootB){
root[rootA] = rootB;
}
else{
root[rootB] = rootA;
}
}
bool find(int a, int b){
int rootA = getRoot(a);
int rootB = getRoot(b);
if(rootA == rootB) return true;
else return false;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i <= n; i++){
root[i] = i;
}
for(int i = 0; i < m; i++){
int q, a, b;
cin >> q >> a >> b;
if(q == 0){
unionNode(a, b);
}
else{
if(find(a, b)){
cout << "YES" << '\n';
}
else{
cout << "NO" << '\n';
}
}
}
return 0;
}