[백준 1717] 집합의 표현

Union_Find (유니온 파인드)의 개념을 알고 있으면 금방 풀 수 있는 문제이다.

연산 명령이 0이면 Union 함수를 사용하여 같은 집합으로 묶어주면 되고

연산 명령이 1이면 Find 함수를 사용하여 최상위 부모가 같은지 확인하여

구현하여 풀 수 있는 문제이다.

※ 입력과 출력이 매번 있기 때문에 cin cout 보다는 ※

※ scanf 과 printf를 쓰는 것이 바람직하다. ※

참고하면 좋은 글 :  유니온 파인드란??

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

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

예제 입력 1

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

예제 출력 1

NO
NO
YES

소스코드

#include<cstdio>
 
int parent[1000001];
 
int Find(int x){
    // root인 경우 X를 반환한다.
    if(x == parent[x])
        return x;
    else{
        // 아니면 root를 찾아감
        int p = Find(parent[x]); 
        parent[x] = p;
        return p;
    }
}
 
void Union(int x, int y){
    x = Find(x);            // x의 최상위 부모 
    y = Find(y);            // y의 최상위 부모 
    
    if(x != y)
        parent[y] = x;        // y의 최상위 부모를 x로 저장한다. 
}
int main(void){
    int n,m, op, a, b;
    
    scanf("%d%d",&n,&m);
    
    // 초기화 
    for(int i = 1; i <= n; i++){
        parent[i] = i;        
    }
    while(m--){
        scanf("%d%d%d",&op,&a,&b);
        if(op == 0){        // 0이면 합치는 연산 
            Union(a,b);
        }
        else if(op == 1){    // 1이면 a와 b가 같은 집합에 속하는지 검사하는 연산 
            int parent_a = Find(a);
            int parent_b = Find(b);
            
            if(parent_a == parent_b)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.