알고리즘/C++
[C++] BAEKJOON 1717 집합의 표현
ssung.k
2019. 9. 22. 22:45
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
유니온 파인드 알고리즘으로 문제를 해결하였습니다.
유니온 파인드를 구현하는 기본적인 문제입니다.
[Algorithm] 유니온 파인드(Union - Find)
유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집..
ssungkang.tistory.com
#include <iostream>
using namespace std;
int parent[1000000];
int Find(int a){
if (parent[a] == a) return a;
else {
int b= Find(parent[a]);
parent[a] = b;
return b;
}
}
void Union(int a,int b){
b = Find(b);
a = Find(a);
if (a!=b)
parent[b] = a;
}
int main(int argc, const char * argv[]) {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
for (int i=1;i<=n;i++){
parent[i] = i;
}
for (int i=0;i<m;i++){
int oper;
int a,b;
cin >> oper >> a >> b;
if (oper == 0){
Union(a,b);
}
else{
if (Find(a) == Find(b)) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
}
return 0;
}