LA3027 合作网络-并查集压缩路径

有N个结点

一次 I u v 操作表示把结点u的父结点设为v,距离为|u-v|%1000.输入保证执行指令前u没有父结点

一次E u 操作表示询问u到根结点的距离

O操作表示结束

 #include<iostream>
 #include<cstring>
 #include<cmath>
 using namespace std;
 ;
 int T,n,level,d[maxn],fa[maxn];
 void init()
 {
     memset(d,,sizeof(d));
     ;i<=n;i++) fa[i]=i;
 }
 int find(int x){
     if(fa[x]==x) return x;
     int ans=find(fa[x]);
     level+=d[x];
     d[x]=level;
     fa[x]=ans;
     return ans;
 }
 int main()
 {
     char op;
     cin>>T;
     while(T--){
         cin>>n;
         init();
         while(cin>>op){
             if(op=='O') break;
             else if(op=='I'){
                 int u,v;
                 cin>>u>>v;
                 d[u]=abs(u-v)%,fa[u]=v;
             }else if(op=='E'){
                 int x;cin>>x;
                 if(fa[x]==x){
                     cout<<<<endl;continue;
                 }
                 level=;
                 find(x);
                 cout<<d[x]<<endl;
             }
         }
     }
     ;
 }
上一篇:程序员晋级CTO之路的8大准则


下一篇:zoj 3822(概率dp)