并查集
作者:
逸.
,
2022-08-12 11:50:02
,
所有人可见
,
阅读 180
并查集模板
核心函数(查找)
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
合并
if (find(a) != find(b)) p[find(b)] = find(a);
全部代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N], a, b;
char op;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
while (m--) {
cin >> op >> a >> b;
if (op == 'M') {
if (find(a) != find(b)) p[find(b)] = find(a);
}
if (op == 'Q') {
if (find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}