src/dsu.hpp

View this file on GitHub
Last update: 2025-10-07 04:08:36+09:00
Include: #include "src/dsu.hpp"

Depends on

src/template.hpp

Verified with

src/test/aoj_DSL_1_A.cpp

Code

#include "template.hpp"

struct dsu {
    vector<int> p;
    dsu(int n): p(n, -1) {}
    bool same(int a, int b) { return leader(a) == leader(b); }
    int leader(int a) { return p[a] < 0 ? a : p[a] = leader(p[a]); }
    int size(int a) { return -p[leader(a)]; }
    int merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(a == b) return a;
        if(p[a] > p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        return a;
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 2 "src/dsu.hpp"

struct dsu {
    vector<int> p;
    dsu(int n): p(n, -1) {}
    bool same(int a, int b) { return leader(a) == leader(b); }
    int leader(int a) { return p[a] < 0 ? a : p[a] = leader(p[a]); }
    int size(int a) { return -p[leader(a)]; }
    int merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(a == b) return a;
        if(p[a] > p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        return a;
    }
};