[ BOJ 백준 1717번 - 집합의 표현 ] 해설 및 코드

https://www.acmicpc.net/problem/1717

 

목적

a,b 두 원소가 포함된 집합을 합치거나, 하나의 집합에 포함되어 있는지 확인하자.

 

접근법

1. 분리집합 기본 문제이다. 

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int LEN = 1e6 + 1;
int a[LEN];
 
int root(int i) {
    while (i != a[i])a[i] = a[a[i]], i = a[i];
    return i;
}
 
void connect(int i, int j) {
    i = root(i), j = root(j);
    if (i == j)return;
    a[i] = j;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    f(i, 0, n + 1)a[i] = i;
    while (m--) {
        int c, a, b; cin >> c >> a >> b;
        if (c)cout << (root(a) == root(b) ? "YES" : "NO") << '\n';
        else connect(a, b);
    }
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.