每次总有新领悟。。
认为没堆最底层为祖先。
关于findset是怎么维护的，这次又好好理解了一下，这道题是每次更新x和x的上一层的结点，自底层向上(从祖先一层一层到本身)。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip> 10 #include<climits> 11 #include<string.h> 12 #include<cmath> 13 #include<stdlib.h> 14 #include<vector> 15 #include<stack> 16 #include<set> 17 #define INF 1e7 18 #define MAXN 10010 19 #define maxn 1000010 20 #define Mod 1000007 21 #define N 1010 22 using namespace std; 23 typedef long long LL; 24 25 int n, m; 26 int fa[333333]; 27 int num[333333]; 28 int un[333333]; 29 30 //取每一堆最底部的为祖先 31 //从祖先向下一层一层更新 32 int findset(int x) 33 { 34 if (x == fa[x]) return x; 35 int tmp = findset(fa[x]); 36 un[x] += un[fa[x]]; 37 fa[x] = tmp; 38 return fa[x]; 39 } 40 41 void merg(int a, int b) 42 { 43 int x = findset(a); 44 int y = findset(b); 45 if (x != y) { 46 un[x] = num[y]; 47 num[y] += num[x]; 48 fa[x] = y; 49 } 50 } 51 52 int main() 53 { 54 int a, b; 55 char ch; 56 while (~scanf("%d",&n)) { 57 getchar(); 58 for (int i = 0; i <= n; ++i) 59 fa[i] = i, num[i] = 1,un[i] = 0; 60 61 for (int i = 0; i < n; ++i) { 62 scanf("%c ",&ch); 63 if (ch == 'M') { 64 scanf("%d%d",&a,&b); 65 getchar(); 66 merg(a, b); 67 } 68 else { 69 scanf("%d",&a); 70 getchar(); 71 findset(a); 72 printf("%d ",un[a]); 73 } 74 } 75 } 76 return 0; 77 }