HDU 3635 并查集+路径压缩+记录每个点移动次数
题意:
给定n个点 oper个操作
每个点有1个龙珠
下面2种操作:
T u v 把u点所有龙珠搬到v
Q u 问u点当前所在城市 u点所在城市有几个龙珠 u点被移动几次
思路:
并查集可以求出 u 点所在城市,记录每个点的 son(子节点数)可以求出 某城市的龙珠数量
用step 记录每个点被移动了几次
#include<stdio.h> #include<string.h> inline int Max(int a,int b){return a>b?a:b;} #define N 100001 struct node{ int step, parent, son; }a[N]; char s[2]; int find(int x){ if(x==a[x].parent)return x; int temp = a[x].parent; a[x].parent = find(a[x].parent); a[x].step += a[temp].step; return a[x].parent; } void Union(int x, int y){ int fx = find(x), fy = find(y); if(fx == fy)return; a[fx].parent = fy; a[fx].step ++; a[fy].son += a[fx].son; a[fx].son = 0; } int main(){ int T, Cas = 1, n, oper, i, j, u, v; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&oper); printf("Case %d: ", Cas++); for(i = 1; i<= n; i++) { a[i].son = 1; a[i].parent = i; a[i].step = 0; } while(oper--){ scanf("%s",s); if(s[0] == 'T') { scanf("%d %d",&u,&v); Union(u, v); } else { scanf("%d",&u); int ans = find(u); printf("%d %d %d ",ans, a[ ans ].son, a[u].step); } } } return 0; }