1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
- 간단한 유니온 파인드 문제이다.
- find 의 경우 path compression 을 통해 경로에 속한 원소들의 부모를 루트로 설정해주면 수행시간이 짧아진다.
- union 에서 어떤 집합을 부모로 할지는 중요하지 않다.
- 입력이 많기 때문에 iostream 을 통해 입출력을 받으면 백준에서 시간초과가 뜨므로, stdio 를 사용하자.
#include <cstdio>
#include <vector>
using namespace std;
int n, m, t, a, b;
vector<int> idx(1000001, -1);
int find_(int cur)
{
if(idx[cur] == -1) return cur; // 루트일 경우 값 반환
idx[cur] = find_(idx[cur]); // 경로에 있는 모든 원소를 루트 바로 밑 자식으로 설정
return idx[cur]; // 루트 값 반환
}
void union_(int x, int y)
{
int rt1 = find_(x); // 각 원소의 루트값을 받아옴
int rt2 = find_(y);
if(rt1 != rt2) idx[rt2] = rt1; // 다른 집합에 속했다면 아무렇게나 집합 합쳐줌
}
int main(void)
{
scanf("%d %d", &n, &m);
for(int i = 0 ; i < m ; i++)
{
scanf("%d %d %d", &t, &a, &b);
if(t) printf((find_(a) == find_(b) ? "YES\n" : "NO\n")); // 1 일 경우 같은 집합인지 확인
else union_(a, b); // 0 일 경우 두 집합을 합쳐줌
}
}
'PS > BOJ' 카테고리의 다른 글
[백준] 1167 : 트리의 지름 (0) | 2021.05.15 |
---|---|
[백준] 1449 : 수리공 항승 (0) | 2021.05.14 |
[백준] 12852 : 1로 만들기 2 (0) | 2021.05.11 |
[백준] 2263 : 트리의 순회 (0) | 2021.05.07 |
[백준] 11404 : 플로이드 (0) | 2021.05.06 |