unionfind/test/potentialized_unionfind.test.cpp

• View this file on GitHub
• Last update: 2024-10-02 23:55:49+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp

Depends on

• Potentialized UnionFind （重み付き UnionFind） (unionfind/potentialized_unionfind.hpp)

Code

#include "../potentialized_unionfind.hpp"
#include <iostream>
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp"
using namespace std;

int main() {
    int N, Q, x, y, z;
    cin >> N >> Q;
    PotentializedUnionFind<int> uf(N);
    for (int i = 0; i < Q; i++) {
        int c;
        cin >> c;
        if (c) {
            cin >> x >> y;
            if (uf.same(x, y)) {
                cout << uf.diff(x, y) << endl;
            } else {
                cout << "?" << endl;
            }
        } else {
            cin >> x >> y >> z;
            uf.unite(x, y, z);
        }
    }
}

#line 2 "unionfind/potentialized_unionfind.hpp"
#include <numeric>
#include <utility>
#include <vector>

// Potentialized UnionFind (Weighted UnionFind)
template <class S> struct PotentializedUnionFind {
    std::vector<int> par, sz;
    std::vector<S> pot;
    PotentializedUnionFind(int N = 0) : par(N), sz(N, 1), pot(N) {
        std::iota(par.begin(), par.end(), 0);
    }
    int find(int x) {
        if (par[x] != x) {
            int r = find(par[x]);
            pot[x] = pot[x] + pot[par[x]], par[x] = r;
        }
        return par[x];
    }
    bool unite(int s, int t, S rel_diff) {
        // Relate s and t by f[t] = f[s] + rel_diff
        // Return false iff contradiction happens.
        rel_diff = rel_diff + weight(s) + (-weight(t));
        if ((s = find(s)) == (t = find(t))) return rel_diff == 0;
        if (sz[s] < sz[t]) std::swap(s, t), rel_diff = -rel_diff;
        par[t] = s, sz[s] += sz[t], pot[t] = rel_diff;
        return true;
    }
    S weight(int x) { return find(x), pot[x]; }
    S diff(int s, int t) { return weight(t) + (-weight(s)); } // return f[t] - f[s]
    int count(int x) { return sz[find(x)]; }
    bool same(int s, int t) { return find(s) == find(t); }
};
#line 2 "unionfind/test/potentialized_unionfind.test.cpp"
#include <iostream>
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp"
using namespace std;

int main() {
    int N, Q, x, y, z;
    cin >> N >> Q;
    PotentializedUnionFind<int> uf(N);
    for (int i = 0; i < Q; i++) {
        int c;
        cin >> c;
        if (c) {
            cin >> x >> y;
            if (uf.same(x, y)) {
                cout << uf.diff(x, y) << endl;
            } else {
                cout << "?" << endl;
            }
        } else {
            cin >> x >> y >> z;
            uf.unite(x, y, z);
        }
    }
}

Back to top page