# # 并查集

## # 练习题

### #BS - Graph Weight Queries (opens new window)

#include "solution.hpp"
using namespace std;

class Solution {
vector<int> p, sz;
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void connect(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv)
return;
if (sz[pu] >= sz[pv]) {
p[pv] = pu;
sz[pu] += sz[pv];
} else {
p[pu] = pv;
sz[pv] += sz[pu];
}
}
public:
int solve(vector<vector<int>>& edges, vector<vector<int>>& queries) {
int n = edges.size();
p = vector<int>(n << 1);
sz = vector<int>(n << 1, 1);
for (int i = 0; i < (n << 1); ++i)
p[i] = i;
auto cmp = [](vector<int> &a, vector<int> &b){
return a[2] < b[2];
};
sort(edges.begin(), edges.end(), cmp);
sort(queries.begin(), queries.end(), cmp);
int idx = 0, ans = 0;
for (auto q : queries) {
while (idx < n && edges[idx][2] <= q[2]) {
connect(edges[idx][0], edges[idx][1]);
idx++;
}
if (find(q[0]) == find(q[1]))
ans++;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44