/*
有N个企业，每个企业想要实现通信，要用线路来连接，线路的长度为abs(a-b)%1000;
如果企业a 链接到了企业b 那么b就是the center of the serving!
然后有两种操作：
E a ： 输出企业a到serving center 的线路的距离
I a, b 将企业a连接到企业 b，那么b就成为了serving center（之前连接a的企业，他们的serving center也变成了b）
思路：并查集！ （压缩路径时回溯求解） ！
*/
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define M 20005
using namespace std;
int n;
int f[M];
int ans[M];//节点 i到 serving center的距离！
int getFather(int x){
if(x==f[x]) return x;
int ff=getFather(f[x]);
ans[x]+=ans[f[x]];//节点x到serving center 的距离要加上其父节点到serving center的距离！
return f[x]=ff;
}
void Union(int a, int b){
if(a==b) return;
f[a]=b;
ans[a]=abs(a-b) % 1000;
}
int main(){
int t;
char ch[3];
cin>>t;
while(t--){
cin>>n;
int a, b;
memset(ans, 0, sizeof(ans));
for(int i=1; i<=n; ++i)
f[i]=i;
while(cin>>ch && ch[0]!='O'){
if(ch[0]=='E'){
cin>>a;
getFather(a);
cout<<ans[a]<<endl;
}
else{
cin>>a>>b;
Union(a, b);
}
}
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3902548.html，如需转载请自行联系原作者
![[POJ 1236] Network of Schools | Tarjan缩点](https://ucc.alicdn.com/pic/developer-ecology/5061455e3b1a4fa2889be2fab9472b9b.png?x-oss-process=image/resize,h_160,m_lfit)