并查集算法的模版代码
C++ 代码
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
class DSU {
public:
DSU(int n) : p_(n) { iota(begin(p_), end(p_), 0); }
int Find(int x) {
if (p_[x] != x) p_[x] = Find(p_[x]);
return p_[x];
}
void Union(int x, int y) {
p_[Find(x)] = p_[Find(y)];
}
private:
vector<int> p_;
};
int main() {
int n, m;
cin >> n >> m;
DSU dsu(n + 1);
char action;
int u, v;
while (m--) {
cin >> action >> u >> v;
switch (action) {
case 'M': dsu.Union(u, v); break;
case 'Q':
cout << (dsu.Find(u) == dsu.Find(v) ? "Yes" : "No") << endl;
break;
}
}
return 0;
}
写的真好!