cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/datastructure/union_find/linked_union_find/past202203_h.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/past202203-open/tasks/past202203_h"

#include <iostream>

#include "library/datastructure/union_find/linked_union_find.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    suisen::LinkedUnionFind uf(n);
    
    while (q --> 0) {
        int query_type;
        std::cin >> query_type;
        if (query_type == 1) {
            int u, v;
            std::cin >> u >> v;
            --u, --v;
            uf.merge(u, v);
        } else {
            int u;
            std::cin >> u;
            --u;
            auto ans = uf.connected_component(u);
            std::sort(ans.begin(), ans.end());
            int len = ans.size();
            for (int i = 0; i < len; ++i) {
                std::cout << ans[i] + 1;
                if (i != len - 1) std::cout << ' ';
            }
            std::cout << '\n';
        }
    }
    return 0;
}
#line 1 "test/src/datastructure/union_find/linked_union_find/past202203_h.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/past202203-open/tasks/past202203_h"

#include <iostream>

#line 1 "library/datastructure/union_find/linked_union_find.hpp"



#include <numeric>
#line 1 "library/datastructure/union_find/union_find.hpp"



#include <algorithm>
#include <vector>

namespace suisen {
    struct UnionFind {
        UnionFind() = default;
        explicit UnionFind(int _n) : _n(_n), _dat(_n, -1) {}
        // Get the root of `x`. equivalent to `operator[](x)`
        int root(int x) {
            static std::vector<int> buf;
            while (_dat[x] >= 0) buf.push_back(x), x = _dat[x];
            while (buf.size()) _dat[buf.back()] = x, buf.pop_back();
            return x;
        }
        // Get the root of `x`. euivalent to `root(x)`
        int operator[](int x) {
            return root(x);
        }
        // Merge two vertices `x` and `y`.
        bool merge(int x, int y) {
            x = root(x), y = root(y);
            if (x == y) return false;
            if (_dat[x] > _dat[y]) std::swap(x, y);
            _dat[x] += _dat[y], _dat[y] = x;
            return true;
        }
        // Check if `x` and `y` belongs to the same connected component.
        bool same(int x, int y) {
            return root(x) == root(y);
        }
        // Get the size of connected componet to which `x` belongs.
        int size(int x) {
            return -_dat[root(x)];
        }
        // Get all of connected components.
        std::vector<std::vector<int>> groups() {
            std::vector<std::vector<int>> res(_n);
            for (int i = 0; i < _n; ++i) res[root(i)].push_back(i);
            res.erase(std::remove_if(res.begin(), res.end(), [](const auto& g) { return g.empty(); }), res.end());
            return res;
        }
    protected:
        int _n;
        std::vector<int> _dat;
    };
} // namespace suisen


#line 6 "library/datastructure/union_find/linked_union_find.hpp"

namespace suisen {
    struct LinkedUnionFind : public UnionFind {
        LinkedUnionFind() = default;
        explicit LinkedUnionFind(int n) : UnionFind(n), _link(n) {
            std::iota(_link.begin(), _link.end(), 0);
        }
        // Merge two vertices `x` and `y`.
        bool merge(int x, int y) {
            if (UnionFind::merge(x, y)) {
                std::swap(_link[x], _link[y]);
                return true;
            }
            return false;
        }
        // Get items connected to `x` (including `x`). Let the size of return value be `m`, time complexity is O(m).
        std::vector<int> connected_component(int x) const {
            std::vector<int> comp{ x };
            for (int y = _link[x]; y != x; y = _link[y]) comp.push_back(y);
            return comp;
        }
    protected:
        std::vector<int> _link;
    };
} // namespace suisen


#line 6 "test/src/datastructure/union_find/linked_union_find/past202203_h.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    suisen::LinkedUnionFind uf(n);
    
    while (q --> 0) {
        int query_type;
        std::cin >> query_type;
        if (query_type == 1) {
            int u, v;
            std::cin >> u >> v;
            --u, --v;
            uf.merge(u, v);
        } else {
            int u;
            std::cin >> u;
            --u;
            auto ans = uf.connected_component(u);
            std::sort(ans.begin(), ans.end());
            int len = ans.size();
            for (int i = 0; i < len; ++i) {
                std::cout << ans[i] + 1;
                if (i != len - 1) std::cout << ' ';
            }
            std::cout << '\n';
        }
    }
    return 0;
}
Back to top page