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

문제 링크 : [백준]집합의 표현(1717)

1717번: 집합의 표현

문제 설명

0부터 N개까지 각각의 수를 원소로 하는 N+1개의 집합({0},{1},...,{N})이 존재합니다.

이 때, M개의 연산이 주어지는데, 다음과 같습니다.

• 0 A B : 숫자 A가 속한 집합과 숫자 B가 속한 집합을 합합니다.(합집합)
• 1 A B : 숫자 A가 속한 집합과 숫자 B가 속한 집합이 같은 집합인지를 출력합니다.

입력

N(원소의 갯수, 1 <= N <= 1,000,000)

M(쿼리의 갯수, 1 <= M <= 100,000)

O A B(쿼리 정보) 

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

 

출력

NO
NO
YES

 

카테고리

#DisjointSet

 

시간 복잡도 상한

O(MlogN)

 

해결 방법

1. DisjointSet을 이용하여 입력 받은 두 수의 그룹을 관리하여 처리합니다.

시간복잡도

O(M)

코드

#include<cstdio>
int n,m,d[1000001],a,b,c;
int f(int a){
    if(a==d[a])return a;
    return d[a]=f(d[a]);
}
void u(int a,int b){
    d[f(a)]=f(b);
}
int main(){
    for(n=1;n<1000001;n++)d[n]=n;
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        if(a)printf("%s\n",f(b)==f(c)?"YES":"NO");
        else u(b,c);
    }
}