Machineboy空
1717: 집합의 표현 - Union-Find Tree 본문
https://www.acmicpc.net/problem/1717
문제요약
- 0 a b : a가 포함되어 있는 집합과, 가 포함되어 있는 집합을 합친다.
- 1 a b : 두 원소가 같은 집합에 포함되어 있는지를 확인한다.
난이도
Gold 5
풀이 포인트
- Union-Find Tree
REVIEW
DP를 썼다고 함. 무슨 소린지 아직 파악 전.
CODE
// 코테 통과는 백트래킹까지만 알면되고! 유니온 파인드 부터는 킬러 문항으로 나옴!
// Union은 합집합, Find: 그룹의 대표찾기!
// DP기법의 두 가지 기법 중 하나로, 메모리자이제이션?
#include <bits/stdc++.h>
using namespace std;
int n, m;
int par[1000001];
// 0: 합집합, 1: Find
// 대표를 리턴하는 연산
void init(){
// 모든 노드가 자기 자신으로 초기화
for(int i = 0; i <1000001; ++i){
par[i] = i;
}
}
int Find(int x){
// 그룹 대표 찾기,
if(x==par[x]) return x;
return par[x] = Find(par[x]); // 이 결과를 날아가지 않게 저장하면 된다!
}
void Union(int a, int b){
int A = Find(a);
int B = Find(b);
par[A] = B;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
init();
cin >> n >> m;
for(int i = 0; i < m; ++i){
int ch, a, b; cin >> ch >> a >> b;
if(ch == 0){
Union(a,b);
}else{
if(Find(a) == Find(b)){
cout << "YES\n";
}else{
cout << "NO\n";
}
}
}
}
'Computer > Coding Test' 카테고리의 다른 글
C++ 문법 기초다지기 예제 모음2 - 연산 (0) | 2024.10.23 |
---|---|
C++ 문법 기초다지기 예제 모음1 - 입력, 프로세싱, 출력 (1) | 2024.10.23 |
15649: N과 M(1) - 백트래킹 (2) | 2024.07.22 |
입력값과 같은 구성의 수 중 가장 작은 큰 수: NextPermutation (0) | 2024.07.08 |
1813: 논리학 교수 - Ad Hoc (0) | 2024.07.02 |