有標號為1到n的n個龍珠，分別放在對應標號為1到n的n個城市里。 下面有兩種操作: T A B表示把A龍珠所在城市的所有龍珠都轉移到B龍珠所在的城市中 Q A 表示查詢A，需要知道A龍珠現在所在的城市，A所在的城市有幾顆龍珠，A轉移到這個城市移動了多少次,分別輸出3個整數，表示上述信息。

前兩個用普通并查集就能算出來，移動次數不好維護；

如果我們不進行路徑壓縮，那么查詢點的深度即是移動的次數，因為每移動一次父節點就下降一層，深度+1；

但不路徑壓縮的話就會超時，所以我們要把點的深度記錄下來；；

#include <cstdio> #include <algorithm> #include <iostream>using namespace std; int ans[100000] ,ansn[100000] ,pre[100000];void init( int x){for( int i = 0 ; i<=x ;i++){pre[i] = i;ans[i] = 0;ansn[i] = 1;} }int find( int a){/* int r=a; //剛開始這樣記錄深度ans[a]，但是這樣不對，這樣只是路徑壓縮一次ans[n]++，但實際上一次可能壓縮很多層，所以應該是加上上一層的壓縮層數while( pre[a]!=a){a=pre[a];}int t;while( pre[r]!=a){ans[r]++;t= pre[r];pre[r] =a;r=t;}*/if( a == pre[a] )return a;else{int tmp= pre[a];pre[a] = find( pre[a]);ans[a] += ans[tmp];}return pre[a]; }int add( int a ,int b){int x=find(a);int y=find(b);if( x != y){pre[x] = y;ans[x] = 1;ansn[y] += ansn[x];ansn[x] =0;} }int main( ){int ks=0, T;scanf("%d",&T);while( T--){printf("Case %d:\n",++ks);int n,m;scanf("%d%d" ,&n ,&m);init( n);while( m--){char op[10];int a,b;scanf("%s",op);if( op[0] == 'T'){scanf("%d%d" ,&a,&b);add( a,b);}if( op[0] == 'Q'){scanf("%d" ,&a);int b=find(a);printf("%d %d %d\n" ,b ,ansn[b] ,ans[a]);}}}return 0; }

?

轉載于:https://www.cnblogs.com/-ifrush/p/10661574.html

總結

以上是生活随笔為你收集整理的N - Dragon Balls(并查集+深度的意义的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。