Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <vector>
#include <iostream>
using namespace std;
class UnionFind {
vector<int> pir;
public:
UnionFind(int size) : pir(size, -1) { }
void unite(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (pir[y] < pir[x]) swap(x, y);
pir[x] += pir[y];
pir[y] = x;
}
}
bool same(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
if (pir[x] < 0) {
return x;
} else {
return pir[x] = root(pir[x]);
}
}
int size(int x) {
return -pir[root(x)];
}
};
signed main(signed argc, char *argv[]) {
int n, m;
cin >> n >> m;
vector<int> a(m), b(m), y(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i] >> y[i];
a[i]--;
b[i]--;
}
int q;
cin >> q;
vector<int> v(q), w(q);
for (int i = 0; i < q; ++i) {
cin >> v[i] >> w[i];
v[i]--;
}
vector<vector<pair<int, int>>> edge(200001);
for (int i = 0; i < m; ++i) {
edge[y[i]].push_back(make_pair(a[i], b[i]));
}
vector<vector<pair<int, int>>> query(200001);
for (int i = 0; i < q; ++i) {
query[w[i]].push_back(make_pair(v[i], i));
}
vector<int> ans(q);
UnionFind uf(n);
for (int i = 200000; i >= 0; --i) {
for (int j = 0; j < (int) query[i].size(); ++j) {
ans[query[i][j].second] = uf.size(query[i][j].first);
}
for (int j = 0; j < (int) edge[i].size(); ++j) {
uf.unite(edge[i][j].first, edge[i][j].second);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment