C++ Library for Competitive Programming
/*
* @title データ構造/素集合データ構造/重みつき union-find
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B
*/
#include <iostream>
#include "emthrm/data_structure/union-find/weighted_union-find.hpp"
int main() {
int n, q;
std::cin >> n >> q;
emthrm::WeightedUnionFind<int> union_find(n);
while (q--) {
int query;
std::cin >> query;
if (query == 0) {
int x, y, z;
std::cin >> x >> y >> z;
union_find.unite(x, y, z);
} else if (query == 1) {
int x, y;
std::cin >> x >> y;
if (union_find.is_same(x, y)) {
std::cout << union_find.diff(x, y) << '\n';
} else {
std::cout << "?\n";
}
}
}
return 0;
}
#line 1 "test/data_structure/union-find/weighted_union-find.test.cpp"
/*
* @title データ構造/素集合データ構造/重みつき union-find
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B
*/
#include <iostream>
#line 1 "include/emthrm/data_structure/union-find/weighted_union-find.hpp"
#include <utility>
#include <vector>
namespace emthrm {
template <typename Abelian>
struct WeightedUnionFind {
explicit WeightedUnionFind(const int n, const Abelian ID = 0)
: ID(ID), parent(n, -1), data(n, ID) {}
int root(const int ver) {
if (parent[ver] < 0) return ver;
const int r = root(parent[ver]);
data[ver] += data[parent[ver]];
return parent[ver] = r;
}
bool unite(int u, int v, Abelian wt) {
wt += weight(u);
wt -= weight(v);
u = root(u);
v = root(v);
if (u == v) return false;
if (parent[u] > parent[v]) {
std::swap(u, v);
wt = -wt;
}
parent[u] += parent[v];
parent[v] = u;
data[v] = wt;
return true;
}
bool is_same(const int u, const int v) { return root(u) == root(v); }
int size(const int ver) { return -parent[root(ver)]; }
Abelian diff(const int u, const int v) { return weight(v) - weight(u); }
private:
const Abelian ID;
std::vector<int> parent;
std::vector<Abelian> data;
Abelian weight(const int ver) {
root(ver);
return data[ver];
}
};
} // namespace emthrm
#line 10 "test/data_structure/union-find/weighted_union-find.test.cpp"
int main() {
int n, q;
std::cin >> n >> q;
emthrm::WeightedUnionFind<int> union_find(n);
while (q--) {
int query;
std::cin >> query;
if (query == 0) {
int x, y, z;
std::cin >> x >> y >> z;
union_find.unite(x, y, z);
} else if (query == 1) {
int x, y;
std::cin >> x >> y;
if (union_find.is_same(x, y)) {
std::cout << union_find.diff(x, y) << '\n';
} else {
std::cout << "?\n";
}
}
}
return 0;
}