자료 출처

공부 자료 출처

분리 집합(Union-Find)와 관련된 문제를 풀다 공부의 필요성을 느껴 이번 기회에 공부해보고자 한다.

공부 후

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>


#define endl "\n"

using namespace std;
int n, m;
vector<int> root;

int find_parent(int x) {
    if (root[x] == x) {
        return x;
    }
    else {
        return root[x] = find_parent(root[x]);
    }
}

void union_(int a, int b) {
    int a_result = find_parent(a);
    int b_result = find_parent(b);  
    if (a_result > b_result) {
        root[a_result] = b_result;
    }
    else root[b_result] = a_result;
}

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

    cin >> n >> m;

    for (int i = 0; i <= n; i++) {
        root.push_back(i);
    }

    for (int i = 0; i < m; i++) {
        int k, a, b;
        cin >> k >> a >> b;
        if (k == 0) {
            union_(a, b);
        }
        else if (k == 1) {
            if (find_parent(a) == find_parent(b)) {
                cout << "YES" << endl;
            }
            else cout << "NO" << endl;
        }
    }

    return 0;

}

추가 공부

모든 점이 정점인 1을 가르키고 있는지 확인하는 코드

#include <iostream>
#include <vector>
#define endl "\n"

using namespace std;

int k, v, e;
vector<int> graph;

int find_parent(int x) {
    if (graph[x] == x) {
        return x;
    }
    else {
        return graph[x] = find_parent(graph[x]);
    }
}

void union_(int a, int b) {
    int a_result = find_parent(a);
    int b_result = find_parent(b);
    if (a_result != b_result) {
        graph[a_result] = b_result;
    }
}

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

    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> v >> e;
        graph.clear();
        graph.resize(v + 1);

        // Initializing the graph
        for (int z = 1; z <= v; z++) {
            graph[z] = z;
        }

        for (int j = 0; j < e; j++) {
            int a, b;
            cin >> a >> b;
            union_(a, b);
        }

        // Example of checking if the graph is fully connected (not related to bipartiteness)
        bool is_connected = true;
        int parent = find_parent(1);
        for (int z = 2; z <= v; z++) {
            if (find_parent(z) != parent) {
                is_connected = false;
                break;
            }
        }

        if (is_connected) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }

    return 0;
}