并查集递归和循环的区别
小弟最近写一道题，关于并查集的，但是用循环写就错，递归就对，我不知道哪里除了问题，所以请教各位大牛
题意：给你1~n个城市每个城市有一个球编号与城市编号相同，现在又两种操作1.T X Y 把x气球所在城市的所有气球转移到y气球所在的城市。2.Q X 求出X气球所在的城市编号 城市中气球的总数 X气球移动的次数
思路就是：子结点移动的次数=他的所有父结点的移动次数的总和，用rank记录就可以了。
代码全部给出，其中没注释掉的是AC的，但是循环那个路劲压缩替换掉递归的就wa了
[code=C/C++][/code]#include<stdio.h>
const int MAXN=10010;
int n,m;
int father[MAXN];
int rank[MAXN];//记录单个集合的总个数
int num[MAXN];//记录移动了几次
void Make_set()//初始化
{
for(int i=1; i<=n; i++)
{
father[i]=i;
rank[i]=0;
num[i]=1;
}
}
//递归
int Find(int x)//压缩路径+查找祖先
{
int temp;
if(x==father[x]) return x;
temp=father[x];
father[x]=Find(father[x]);
rank[x]+=rank[temp];//
return father[x];
}
/*
//循环
int Find(int x)//压缩路径+查找祖先
{
int k,j,r;
r=x;
while(r!=father[r])
{
r=father[r];
}
k=x;
while(k!=r)//路径压缩
{
rank[k]+=rank[father[k]];//记录子结点与祖先的距离
j=father[k];
father[k]=r;
k=j;
}
return r;
}
*/
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x==y) return ;
father[x]=y;
rank[x]++;
num[y]+=num[x];//根结点为y的龙珠总共有几个
num[x]=0;
}
int main()
{
int T;
char ch[2];
int a,b;
int cas=1;
scanf("%d",&T);
while(T--)
{
printf("Case %d:\n",cas++);
scanf("%d%d",&n,&m);
Make_set();
for(int i=0; i<m; i++)
{
scanf("%s",ch);
if(ch[0]=='T')
{
scanf("%d%d",&a,&b);
if(a==b) continue;
Union(a,b);
}
else
{
scanf("%d",&a);
int x=Find(a);
printf("%d %d %d\n",x,num[x],rank[a]);
}
}
}
return 0;
}
[解决办法]
rank[k]+=rank[father[k]];//记录子结点与祖先的距离
这句和递归的不等价。递归的那句执行下来是从根开始把正确答案往下散播。你这个非递归的这句是从叶子开始往根反向执行，所以统计出来不对。
