题意：
有N个齿轮，三种操作
1.操作L x y：把齿轮x,y链接，若x,y已经属于某个齿轮组中，则这两组也会合并。
2.操作Q x y：询问x,y旋转方向是否相同（等价于齿轮x,y的相对距离的奇偶性）。
3.操作D x ：拆下齿轮x，并且x所在的齿轮组不会断开
4.操作S x ： 查询齿轮x所在的齿轮组有多少齿轮。
并查集，维护父节点的同时，dis记录一下每个节点到根节点的距离，并且用num记录一下以x为根节点的集合有多少个元素。
由于涉及到删除操作，删除的是根节点的话会导致信息丢失，所以在删除的时候直接新建一个节点，所以再加一个变量，表示节点x所对应的实际节点编号mp[x]。
这样fa[x]表示x的父节点，mp[x]表示x实际的编号（从N+1开始记）
（copied）
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; #define N 600007 #define M 33 int fa[N],n,m,dis[N]; int num[N],mp[N]; int findset(int x) { if(x != fa[x]) { int tmp = findset(fa[x]); dis[x] += dis[fa[x]]; //累加距离 fa[x] = tmp; } return fa[x]; } void init() { for(int i=0;i<=n+m;i++) { fa[i] = i; num[i] = 1; dis[i] = 0; mp[i] = i; } } int main() { int i,u,v,k; char ss[5]; while(scanf("%d%d",&n,&m)!=EOF) { init(); int now = n+1; while(m--) { scanf("%s",ss); if(ss[0] == 'L') { scanf("%d%d",&u,&v); u = mp[u]; //实际的位置 v = mp[v]; int fx = findset(u); int fy = findset(v); if(fx != fy) { fa[fx] = fy; //dis[fx] = dis[fy]+1; //1 //dis[u] = dis[v]+1; //2 **1,2顺序不能反，或者直接用下面** dis[fx] = dis[u]+dis[v]+1; //与根距离之和的奇偶性再反一下，得出相对距离的奇偶性 num[fy] += num[fx]; } } else if(ss[0] == 'Q') { scanf("%d%d",&u,&v); u = mp[u]; //实际的位置 v = mp[v]; int fx = findset(u); int fy = findset(v); if(fx != fy) puts("Unknown"); else { if(abs(dis[u]-dis[v]) & 1) puts("Different"); else puts("Same"); } } else if(ss[0] == 'S') { scanf("%d",&u); int tu = mp[u]; printf("%d\n",num[findset(tu)]); } else { scanf("%d",&v); int tv = mp[v]; num[findset(tv)]--; mp[v] = now++; } } } return 0; }