[백준 1717] 집합의 표현 (c++)

문제풀이

union-find를 이용한 문제입니다. paraent를 자기자신으로 초기화 한뒤 계속 한쪽을 붙여주며 붙여주고나서는 parent를 가리키는 방식입니다. 

 

간단한 방식이고 더 효율적으로 푸려면 자식이 많은 트리에 계속 붙여나가고 루트노드에 바로 직접 자식이 붙어있도록 최적화를 한다면 더 빨라 질것 같으나 

 

해당문제에서는 그정도 까지는 필요없다고 판단하여 이렇게 풀었습니다.

소스코드

 
#include <stdio.h>
 
using namespace std;
 
int N,M;
 
int parent[1000001];
 
 
void initSet(){
    for(int i=0;i<=N;i++)
        parent[i] = i;
}
 
int find(int num){
    if (num == parent[num])
        return num;
    else{
        parent[num] = find(parent[num]);
        return parent[num];
    }
}
 
int main() {
    scanf("%d %d",&N,&M);
    initSet();
    for(int i=0;i<M;i++){
        int mode,num1,num2;
        scanf("%d %d %d",&mode,&num1,&num2);
        if(mode==0){
            num1 = find(num1);
            num2 = find(num2);
            if(num1!=num2)
                parent[num2]=num1;
        }
        else{
            num1 = find(num1);
            num2 = find(num2);
            if(num1==num2)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    
    return 0;
}
 

 

 

문제 링크 : https://www.acmicpc.net/problem/1717

1717번: 집합의 표현