문제

문제 링크

어떻게 접근할 것인가?

  • 집합을 합하고 같은 집합인지 확인하는 문제이다.
  • 이러한 문제는 집합의 교집합과 비교에 능한 Union-Find 알고리즘을 이용하면 뚝딱이다.
  • 근데 강화버전을 활용한다면 훨씬 빠르게 문제를 해결할 수 있다.

Union-Find 정리 자료

Union-Find 강화버전 정리 자료

코드

#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <math.h>

using namespace std;

struct subset {
    int parent;
    int rank;
};

struct subset *subsets;

int find(int i){
    if(subsets[i].parent != i)subsets[i].parent = find(subsets[i].parent);
    return subsets[i].parent;
}

void Union(int x, int y){
    int xroot = find(x);
    int yroot = find(y);
    if(subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot;
    else if(subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot;
    else{
        subsets[yroot].parent = xroot;
        subsets[xroot].rank ++;
    }
}

int search(int x, int y){
    int xset = find(x);
    int yset = find(y);
    if(xset == yset) return 1;
    else return 0; 
}


int main(){
    int n,m,c,src,dst;
    scanf("%d %d", &n, &m);
    
    subsets = (struct subset*) malloc( (n+1) * sizeof(struct subset) );
    for (int v = 0; v < n+1; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }


    for(int i = 0; i < m; i ++){
        scanf("%d %d %d", &c, &src, &dst);
        if(c == 0) Union(src, dst);
        
        else {
            if(search(src, dst)) printf("YES\n");
            else printf("NO\n");
        }
    }
}