[ALGORITHM] 백준 1717 - 집합의 표현 (Weighted Union Find)

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

1717번: 집합의 표현

Weighted Union Find란?

par과 rank배열을 각기 사용하게 된다면 메모리 공간을 rank배열만큼 더 잡아먹으므로 그를 줄이기 위해 par의 음수의 절대값은 rank배열의 용도로 사용하는 것. (루트노드가 자기 자신을 가르키는 대신 음수를 가지게 함)

 

단순 Union Find와의 차이

1. 각각의 부모를 저장하는 par배열을 자기 자신의 값이 아닌 -1로 초기화 해준다. (음수는 루트 노드를 뜻하며 그 절대값이 rank(집합의 크기)가 됩니다.)
2. find함수에서 node와 par[node]가 같은지를 찾는게 아닌 par[node]가 음수 값을 가질때 까지 진행
3. 최종적으로 나온 node1값과 node2값 중 더 작은 값을 가진 집합이 크기가 큰 것이므로 더 작은 값을 가진(절대값이 더 큰) 집합쪽에 다른 집합을 연결해줍니다.

코드

#include<iostream>
#include<vector>

using namespace std;

typedef struct data{
    int ord,a,b;
}d;

int n,m;
int par[1'000'007];
vector<d> orders;

void initialize(){
    for(int i=0;i<1'000'007;i++)
        par[i]=-1;
}

void input(){
    cin>>n>>m;

    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        
        orders.push_back({a,b,c});
    }
}

int find(int node){
    if(par[node] < 0) return node;
    return par[node] = find(par[node]);
}

void union_list(int node1, int node2){
    node1 = find(node1);
    node2 = find(node2);

    if(node1==node2)
        return;
    
    if(par[node1] < par[node2]){//루트는 음수의 값을 가짐
        par[node1] += par[node2];
        par[node2] = node1;
    }
    else{
        par[node2] += par[node1];
        par[node1] = node2;
    }
}

bool same(int node1, int node2){
    node1 = find(node1);
    node2 = find(node2);

    if(node1 == node2)
        return true;
    return false;
}

void solution(){
    int ord,a,b;
    for(int i=0;i<orders.size();i++){
        ord=orders[i].ord;
        a=orders[i].a;
        b=orders[i].b;

        if(ord){
            if(same(a,b))
                cout<<"YES"<<'\n';
            else
                cout<<"NO"<<'\n';
        }
        else{
            union_list(a,b);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    initialize();
    input();
    solution();

    return 0;
}