C++ Library for Competitive Programming
/*
* @title データ構造/素集合データ構造/部分永続 union-find
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/agc002/tasks/agc002_d
*/
#include <iostream>
#include <numeric>
#include "emthrm/data_structure/union-find/partially_persistent_union-find.hpp"
int main() {
int n, m;
std::cin >> n >> m;
emthrm::PartiallyPersistentUnionFind union_find(n);
for (int i = 1; i <= m; ++i) {
int a, b;
std::cin >> a >> b;
--a; --b;
union_find.unite(i, a, b);
}
int q;
std::cin >> q;
while (q--) {
int x, y, z;
std::cin >> x >> y >> z;
--x; --y;
int lb = 0, ub = m;
while (ub - lb > 1) {
const int mid = std::midpoint(lb, ub);
(union_find.size(mid, x) + (union_find.is_same(mid, x, y) ?
0 : union_find.size(mid, y)) >= z ? ub : lb) = mid;
}
std::cout << lb + 1 << '\n';
}
return 0;
}
#line 1 "test/data_structure/union-find/partially_persistent_union-find.test.cpp"
/*
* @title データ構造/素集合データ構造/部分永続 union-find
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/agc002/tasks/agc002_d
*/
#include <iostream>
#include <numeric>
#line 1 "include/emthrm/data_structure/union-find/partially_persistent_union-find.hpp"
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
namespace emthrm {
struct PartiallyPersistentUnionFind {
explicit PartiallyPersistentUnionFind(const int n)
: data(n, -1), last(n, -1), history(n, {{-1, -1}}) {}
int root(const int t, const int ver) const {
return last[ver] == -1 || t < last[ver] ? ver : root(t, data[ver]);
}
bool unite(const int t, int u, int v) {
u = root(t, u);
v = root(t, v);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
last[v] = t;
history[u].emplace_back(t, data[u]);
return true;
}
bool is_same(const int t, const int u, const int v) const {
return root(t, u) == root(t, v);
}
int size(const int t, int ver) const {
ver = root(t, ver);
return -std::prev(std::lower_bound(history[ver].begin(),
history[ver].end(),
std::make_pair(t, 0)))->second;
}
private:
std::vector<int> data, last;
std::vector<std::vector<std::pair<int, int>>> history;
};
} // namespace emthrm
#line 12 "test/data_structure/union-find/partially_persistent_union-find.test.cpp"
int main() {
int n, m;
std::cin >> n >> m;
emthrm::PartiallyPersistentUnionFind union_find(n);
for (int i = 1; i <= m; ++i) {
int a, b;
std::cin >> a >> b;
--a; --b;
union_find.unite(i, a, b);
}
int q;
std::cin >> q;
while (q--) {
int x, y, z;
std::cin >> x >> y >> z;
--x; --y;
int lb = 0, ub = m;
while (ub - lb > 1) {
const int mid = std::midpoint(lb, ub);
(union_find.size(mid, x) + (union_find.is_same(mid, x, y) ?
0 : union_find.size(mid, y)) >= z ? ub : lb) = mid;
}
std::cout << lb + 1 << '\n';
}
return 0;
}