题意：
有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=;i<=n+m;i++)
{
fa[i] = i;
num[i] = ;
dis[i] = ;
mp[i] = i;
}
} int main()
{
int i,u,v,k;
char ss[];
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
int now = n+;
while(m--)
{
scanf("%s",ss);
if(ss[] == '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]+; //与根距离之和的奇偶性再反一下，得出相对距离的奇偶性
num[fy] += num[fx];
}
}
else if(ss[] == '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]) & )
puts("Different");
else
puts("Same");
}
}
else if(ss[] == '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 ;
}