//
//  dsu.h
//  sem9
//
//  Created by krymov on 14/12/2018.
//  Copyright © 2018 krymov. All rights reserved.
//

#ifndef dsu_h
#define dsu_h
#include <iostream>
#include <vector>
#include <stack>

class DSU {
public:
    DSU(size_t size) : arr(size), rank(size, 0) {
        for (int i = 0; i < size; ++i) {
            arr[i] = i;
        }
    }
    void union_sets (int a, int b) {
        a = find_set (a);
        b = find_set (b);
        if (a != b) {
            if (size[a] < size[b])
                swap (a, b);
            parent[b] = a;
            rank[a] += rank[b];
        }
    }
    int find_set(int v) {
        assert(v < arr.size());
        std::stack<int> q;
        int cur = arr[v];
        q.push(v);
        while (cur != arr[cur]) {
            q.push(arr[cur]);
            cur = arr[cur];
        }
        int root = cur;
        while (!q.empty()) {
            arr[q.top()] = root;
            q.pop();
        }
        return root;
    }

    void union_set(int a, int b) {
        assert(a < arr.size());
        assert(b < arr.size());

        int set_a = find_set(a);
        int set_b = find_set(b);

        if (set_a != set_b) {
            if (rank[set_a] < rank[set_b]) {
                std::swap(set_a, set_b);
            }
            arr[set_b] = set_a;
            if (rank[set_a] == rank[set_b]) {
                rank[set_a]++;
            }
        }
    }

private:
    std::vector<int> arr;
    std::vector<int> rank;
};

int main2(int argc, const char * argv[]) {
    DSU dsu(10);
    for (int i = 0; i < 10; ++i) {
        std::cout << dsu.find_set(i) << std::endl;
    }
    for (int i = 0; i < 5; ++i) {
        dsu.union_set(i, 9 - i);
    }
    std::cout << "-----------" << std::endl;
    for (int i = 0; i < 10; ++i) {
        std::cout << dsu.find_set(i) << std::endl;
    }

    // insert code here...
    std::cout << "Hello, World!\n";
    return 0;
}

#endif /* dsu_h */