[백준] 1717 | 집합의 표현 | C++

풀이의 핵심은 Union & Find 알고리즘이다.

 

위 그림을 보면,

노드 1, 2, 3이 한 집합,

노드 4, 5가 한 집합으로 엮여있음을 직관적으로 알 수 있다.

 

(추후, 작성하겠습니다.)

 

정답 소스코드

#include<bits/stdc++.h>
using namespace std;

int n, m;
int unf[1000004];

int Find(int v) {
    if(unf[v]==v) return v;
    return unf[v]=Find(unf[v]);
}

void Union(int a, int b) {
     a=Find(a);
     b=Find(b);
     if(a!=b) unf[a]=b;
}

int main() {
    ios_base::sync_with_stdio(0);
    for(int i=1; i<=1000004; i++) unf[i]=i;
    cin>>n>>m;
    int a, b, c;
    while(m--) {
        cin>>a>>b>>c;
        if(a==0) Union(b, c);
        if(a==1) {
            int fb=Find(b);
            int fc=Find(c);
            if(fb==fc) puts("YES");
            if(fb!=fc) puts("NO");
        }
    }
    return 0;
}