传送门
题目大意：有n个龙蛋，分别坐落在n个城市。现在有m个操作。操作分为T，Q。对于T：给出x，y，把x所在的城市中的蛋全部移到y所在城市去。对于Q：给出x，我们需要输出x所在的城市的编号，以及这个城市中的龙蛋数量，还有x移动了的次数
Solution:只需维护三个值：所在城市，龙蛋数量，移动次数。我们用father[i]代表i所在城市编号，cnt[i]代表i城市的龙蛋数量，times[i]代表i移动了多少次。
考虑如何维护：对于father,只需要普通的并查集操作；对于cnt，在每次T操作后，动态更新；对于times，由于需要每个节点的移动次数，如果采用O(n)维护是显然会TLE的，所以考虑在路径压缩时顺便更新即可。
#include<bits/stdc++.h> #define N 10005 using namespace std; int T,n,q,father[N],times[N],cnt[N]; //father[i]:第i个蛋属于哪个城市 times[i]:第i颗蛋移动次数 cnt[i]:第i个城市有多少个蛋 inline int getfather(int x) { if(father[x]==x) return x; int fa=father[x]; father[x]=getfather(father[x]);//其实每个根结点都是最多移动一次的 times[x]+=times[fa]; return father[x]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>T; for(int i=1;i<=T;i++) { cout<<"Case "<<i<<":"<<'\n'; cin>>n>>q; for(int i=1;i<=n;i++){ father[i]=i; times[i]=0; cnt[i]=1; } while(q--) { char opt; int x,y; cin>>opt; if(opt=='T') { cin>>x>>y; int ax=getfather(x); int bx=getfather(y); if(ax!=bx) { father[ax]=bx; cnt[bx]+=cnt[ax]; times[ax]++; } } if(opt=='Q') { cin>>x; int ax=getfather(x); cout<<ax<<" "<<cnt[ax]<<" "<<times[x]<<'\n'; } } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9384772.html
