library

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

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Weighted Union Find
(DataStructure/weightedunionfind.hpp)

• View this file on GitHub
• Last update: 2024-07-20 01:49:00+09:00
• Include: #include "DataStructure/weightedunionfind.hpp"

Verified with

• Verify/AOJ_DSL_1_B.test.cpp

Code

#pragma once

template <typename T> struct WeightedUnionFind {
    int n;
    vector<int> par;
    vector<T> pot;
    WeightedUnionFind(int _n = 0) : n(_n), par(n, -1), pot(n) {}
    int root(int x) {
        if (par[x] < 0)
            return x;
        else {
            int r = root(par[x]);
            pot[x] = pot[par[x]] + pot[x];
            return par[x] = r;
        }
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -par[root(x)];
    }
    T diff(int x, int y) {
        root(x);
        root(y);
        return -pot[y] + pot[x];
    }
    bool unite(int x, int y, T w) {
        int rx = root(x), ry = root(y);
        if (rx == ry)
            return false;
        if (par[rx] < par[ry])
            swap(x, y), swap(rx, ry), w = -w;
        par[ry] += par[rx];
        par[rx] = ry;
        pot[rx] = pot[y] + w - pot[x];
        n--;
        return true;
    }
};

/**
 * @brief Weighted Union Find
 */

#line 2 "DataStructure/weightedunionfind.hpp"

template <typename T> struct WeightedUnionFind {
    int n;
    vector<int> par;
    vector<T> pot;
    WeightedUnionFind(int _n = 0) : n(_n), par(n, -1), pot(n) {}
    int root(int x) {
        if (par[x] < 0)
            return x;
        else {
            int r = root(par[x]);
            pot[x] = pot[par[x]] + pot[x];
            return par[x] = r;
        }
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -par[root(x)];
    }
    T diff(int x, int y) {
        root(x);
        root(y);
        return -pot[y] + pot[x];
    }
    bool unite(int x, int y, T w) {
        int rx = root(x), ry = root(y);
        if (rx == ry)
            return false;
        if (par[rx] < par[ry])
            swap(x, y), swap(rx, ry), w = -w;
        par[ry] += par[rx];
        par[rx] = ry;
        pot[rx] = pot[y] + w - pot[x];
        n--;
        return true;
    }
};

/**
 * @brief Weighted Union Find
 */

Back to top page