백준 01717 - 집합의 표현

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

1717번: 집합의 표현

 

고려사항

• 유니온-파인드 알고리즘(서로소) 사용
• 부모 정보가 담기는 배열을 n+1개 선언
• 두 집합을 합칠 때에는 루트 번호가 작은것이 새로운 루트가 되도록 구현
• 재귀를 활용한 findNum 구현.
• 집합을 합칠 때마다, 매번 집합 원소들의 부모를 전부 업뎃해줄 수는 없으니,
  집합의 루트였던 원소의 부모 정보를 자기 자신에서 새로운 루트로 업데이트 후,
  나중에 원소들의 부모가 같은지 findNum return 값을 비교하여 알아볼때, 재귀로 올라가도록 하는 원리.
• 자신이 속한 집합의 루트가 같은 값이라면, 그 자체가 root이니 반환!

 

#include <iostream>
using namespace std;

int numSet[1000001];

int findNum(int num){
    if(num == numSet[num]){
        return num;
    }else{
        return numSet[num] = findNum(numSet[num]);
    }
}

void unionNum(int num1, int num2){
    int root1 = findNum(num1);
    int root2 = findNum(num2);

    if(root1 < root2){
        numSet[root2] = root1;
    }else{
        numSet[root1] = root2;
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n, m, op, num1, num2, root1, root2;

    cin>>n>>m;
    for(int i=0;i<=n;++i){
        numSet[i] = i;
    }

    for(int i=0;i<m;++i){
        cin>>op>>num1>>num2;

        if(op == 0){
            unionNum(num1, num2);
        }else{
            root1 = findNum(num1);
            root2 = findNum(num2);

            if(root1 == root2){
                cout<<"YES\n";
            }else{
                cout<<"NO\n";
            }
        }
    }
    return 0;
}