- 并查集专题
T1
- @ 2025-8-20 15:52:02
#include<bits/stdc++.h>
using namespace std;
const int N = 30010;
int fa[N], d[N], s[N];
int find(int x)
{
if(fa[x] != x) {
int root = find(fa[x]);
d[x] += d[fa[x]];
fa[x] = root;
}
return fa[x];
}
int main()
{
for(int i = 1; i < N; i++)
{
fa[i] = i;
s[i] = 1;
}
int t;
cin >> t;
while(t --)
{
string op;
int a, b;
cin >> op >> a >> b;
if(op == "M") {
int pa = find(a), pb = find(b);
if(pa == pb) continue;
d[pa] = s[pb];
s[pb] += s[pa];
fa[pa] = pb;
}
else
{
int pa = find(a), pb = find(b);
if(pa != pb) cout << -1 << endl;
else {
cout << max(0, abs(d[a] - d[b]) - 1) << endl;
}
}
}
return 0;
}
0 条评论
目前还没有评论...