这个题做了N长时间……
因为一开始是不会并查集的时候纪录其他东西的，然后就想自己搞一下。
一开始是只会非递归的并查集，所以开了三个数组……
a就是纪录父亲节点的，d是纪录这一堆最下面的节点的，s是记录这个点下面有多少点的。
因为是非递归，所以每次合并之后，必须从堆在上面的那一坨最下面的节点（是用d纪录的）开始再往上更新s数组，所以它是有些慢，必须要保持树的结构的，不能路径压缩的，但是是对滴~
所以对于这个题的11个测试点，它只能过10个……但还是贴一下记录下艰辛的历程……
View Code var d,a:array[0..30000] of longint; s:array[0..30000] of longint; x,y,p,i:longint; ch:char;function find(x:Longint):longint;var k,y,t:longint;begin k:=x;while a[k]<>0 do k:=a[k]; find:=k;end;procedure dos(x,y:longint);var k:longint;begin k:=x;while k<>0 dobegin s[k]:=s[k]+y+1; k:=a[k];end;end;procedure move(l,r:Longint);var i,q:longint;begin p:=find(l); q:=find(r);if p<>q then begin dos(d[p],s[q]); a[q]:=d[p]; d[p]:=d[q];end;end;procedure ask(l:longint);begin writeln(s[l]);end;begin readln(p);for i:=0 to 30000 do d[i]:=i; fillchar(a,sizeof(a),0);for i:=1 to p dobegin read(ch);if ch='M' then begin readln(x,y); move(x,y);end else begin readln(x); ask(x);end;end; close(input); close(output);end.后来和冷学在吃饭的路上讨论起来，就问它怎么更新。冷学说写递归的并查集，回来的时候就可以更新了，非递归的白搭啊。
非递归只是找到父节点就完事了，递归的还需要回溯下，它父亲的值就能回来了，好奇妙~第一次了解两者的区别……
然后听从冷学的建议换着开了数组……
fa表示父亲，sum表示这一坨里有多少数，up表示在这一坨里它顶上有多少数。
并查集的时候要这样：
function find(x:longint);
begin
if fa[x]=0 then exit(x); \\找到根节点
find:=find(fa[x]); \\找根节点
up[x]:=up[x]+up[fa[x]]; \\合并up数组
fa[x]:=find; \\路径压缩
end;
合并的时候和输出的时候再考虑下就行了……这还算是并查集的基础题吧结果这么费事，内牛满面……
View Code var up,sum,fa:array[1..30000] of longint; ch:char; p,i,x,y:longint;procedure init;var i:longint;beginfor i:=1 to 30000 dobegin fa[i]:=0; up[i]:=0; sum[i]:=1;end;end;function find(x:longint):longint;beginif fa[x]=0 then exit(x); find:=find(fa[x]); up[x]:=up[x]+up[fa[x]]; fa[x]:=find;end;procedure move(l,r:longint);var p,q:longint;begin q:=find(l); p:=find(r);if p<>q then begin fa[p]:=q; up[p]:=sum[q]; sum[q]:=sum[q]+sum[p];end;end;procedure ask(x:longint);var r:longint;begin r:=find(x); writeln(sum[r]-up[x]-1);end;begin init; readln(p);for i:=1 to p dobegin read(ch);if ch='M' then begin readln(x,y); move(x,y);end else begin readln(x); ask(x);end;end;end.转载于:https://www.cnblogs.com/zjerly/archive/2011/10/26/2225646.html
