Test/LC/unionfind.test.cpp

View this file on GitHub
Last update: 2025-05-05 21:42:21+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"

#include <iostream>

int main() {
    using namespace zawa;
    SetFastIO();
    u32 n, q; std::cin >> n >> q;
    DisjointSetUnion dsu(n);
    for (u32 _{} ; _ < q ; _++) {
        u32 t, u, v; std::cin >> t >> u >> v;
        if (t == 0) {
            dsu.merge(u, v);
        }
        else {
            std::cout << dsu.same(u, v) << '\n';
        }
    }
}

#line 1 "Test/LC/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Template/IOSetting.hpp"

#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"

#line 4 "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"

#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
#include <concepts>

namespace zawa {

class DisjointSetUnion {
public:
    DisjointSetUnion() = default;

    DisjointSetUnion(usize n) : n_{n}, comps_{n}, data_(n, -1) {
        data_.shrink_to_fit();
    }
    
    u32 leader(u32 v) {
        return data_[v] < 0 ? v : static_cast<u32>(data_[v] = leader(data_[v]));
    }

    bool same(u32 u, u32 v) {
        return leader(u) == leader(v);
    }

    bool merge(u32 u, u32 v) {
        assert(u < n_);
        assert(v < n_);
        u = leader(u);
        v = leader(v);
        if (u == v) return false;
        comps_--;
        if (data_[u] > data_[v]) std::swap(u, v);
        data_[u] += data_[v];
        data_[v] = u;
        return true;
    }

    inline usize size() const noexcept {
        return n_;
    }

    usize size(u32 v) {
        assert(v < n_);
        return static_cast<usize>(-data_[leader(v)]);
    }

    inline usize components() const noexcept {
        return comps_;
    }

    template <class T = usize>
    std::vector<std::vector<T>> enumerate() requires std::convertible_to<usize, T> {
        std::vector<std::vector<T>> res(n_);
        for (usize v{} ; v < n_ ; v++) {
            res[leader(v)].push_back(static_cast<T>(v));
        }
        std::erase_if(res, [](const auto& arr) -> bool { return arr.empty(); });
        return res;
    }

private:
    usize n_{}, comps_{};
    std::vector<i32> data_;
};

} // namespace zawa
#line 6 "Test/LC/unionfind.test.cpp"

#line 8 "Test/LC/unionfind.test.cpp"

int main() {
    using namespace zawa;
    SetFastIO();
    u32 n, q; std::cin >> n >> q;
    DisjointSetUnion dsu(n);
    for (u32 _{} ; _ < q ; _++) {
        u32 t, u, v; std::cin >> t >> u >> v;
        if (t == 0) {
            dsu.merge(u, v);
        }
        else {
            std::cout << dsu.same(u, v) << '\n';
        }
    }
}