算法
(并查集按秩合并) $O(N(\log N)^2 + Q\log N)$
题意:
- 操作1:合并学生 $x$ 和学生 $y$ 所在群组
- 操作2:查询学生 $x$ 所在群组中有多少是班级 $y$ 的学生
分析:
只需在并查集的板子上添加按秩合并以及维护每个人当前所在群组的每个班的人数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::swap;
using std::vector;
struct UnionFind {
vector<int> par;
vector<map<int, int>> mp;
UnionFind(int n=0): par(n, -1), mp(n) {}
int find(int x) {
if (par[x] < 0) return x;
return par[x] == find(par[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (par[x] > par[y]) swap(x, y);
// x > y
for (auto p : mp[y]) {
mp[x][p.first] += p.second;
}
mp[y] = map<int, int>();
par[x] += par[y];
par[y] = x;
return true;
}
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -par[find(x)]; }
};
int main() {
int n, q;
cin >> n >> q;
UnionFind t(n);
rep(i, n) {
int c;
cin >> c;
t.mp[i][c] = 1;
}
rep(qi, q) {
int type;
cin >> type;
if (type == 1) {
int a, b;
cin >> a >> b;
--a; --b;
t.unite(a, b);
}
else {
int x, y;
cin >> x >> y;
--x;
x = t.find(x);
int ans = t.mp[x][y];
cout << ans << '\n';
}
}
return 0;
}
以后跟大佬混了