https://www.luogu.org/problem/show?pid=1196
改一下普通的并查集就可以了
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ms(i,j) memset(i, j, sizeof i); const int maxn = 30005; int father[maxn];//并查集 int h[maxn];//后面有多少船(包括这个船) int f[maxn];//前面有多少船 int T; int abss(int x) { return x>=0 ? x : -x; } int find(int x) { if (father[x]==x) return x; int fx = find(father[x]);//要先递归 f[x] += f[father[x]];//前面的值 return father[x]=fx;//路径压缩 } int merge(int x, int y) { int a = find(x); int b = find(y); father[a] = b; f[a] = h[b];//前面的值 h[b] += h[a];//后面的值 } int check(int x, int y) { int a = find(x); int b = find(y); if (a!=b) return -1; else return abss(f[x]-f[y])-1; } int solve() { int i,j; char ch; scanf("%d\n", &T); while (T--) { scanf("%c %d%d\n", &ch, &i, &j); if (ch=='M') merge(i,j); else if (ch=='C') printf("%d\n", check(i,j)); } } int init() { for (int i=1;i<=maxn;i++) { father[i] = i; h[i] = 1; f[i] = 0; } } int main() { init(); solve(); return 0; }