Union Find Basic Code C++

Union Find를 이해하기 위한 기본 코드

 

findTopnode를 통해서 최상단 노드를 알 수 있다

union_node를 통해서 입력된 수의 최상단노드를 찾아 두 수를 연결해주는 작업을 한다

check_node를 통해서 두 수가 서로 연결 되었는지 알 수 있다

www.cs.usfca.edu/~galles/visualization/DisjointSets.html

Disjoint Sets Visualization

위 사이트에서 눈으로 직접 보면서 이해할 수 있다!! 좋음

#include <iostream>
#include <vector>
using namespace std;
 
int findTopnode(vector<int> node, int x){
    if(node[x] == x){
        return x;
    }
    return findTopnode(node, node[x]);
}
 
void union_node(vector<int> &node, int a, int b){
    a = findTopnode(node, a);
    b = findTopnode(node, b);
    if(a < b){
        node[b] = a;
    }
    else{
        node[a] = b;
    }
}
 
bool check_node(vector<int> node, int a, int b){
    a = findTopnode(node, a);
    b = findTopnode(node, b);
    if(a == b){
        return true;
    }
    else{
        return false;
    }
}
 
int main(){
    vector<int> Node;
    Node.push_back(0);
 
    for(int i = 1; i <= 10; i++){
        Node.push_back(i);
    }
    union_node(Node, 1, 2);
    union_node(Node, 2, 3);
    union_node(Node, 3, 4);
    union_node(Node, 5, 6);
    union_node(Node, 7, 8);
 
    if(check_node(Node, 1, 5)){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    union_node(Node, 4, 5);
 
    if(check_node(Node, 1, 5)){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    for(int i = 0; i < Node.size(); i++){
        cout << Node[i] << "\n";
    }
    // for(auto w : Node){
    //     cout << w << " ";
    // }
    cout << "\n" << findTopnode(Node, 6);
    return 0;
}