两个用递归写的并查集的问题

This topic created in 4102 days ago, the information mentioned may be changed or developed.

问题一：
找根的函数，我写的代码：
int getfather(int n)
{
　　if(father[n]==n) return n;
　　else getfather(father[n]);
}
标程：
int Find(int n) {
if (father[n] == n) return n;
father[n] = Find(father[n]);
return father[n];
}

我觉得我写的函数如果根不是自己就找父节点，如果父节点的根还不是自己，还是可以往上找啊...感觉自己写的似乎没有错...

问题二:
题目： https://vijos.org/p/1034
按照标程我改了那个函数...依然是几乎所有点 Wrong Answer .....程序如下，和标程对比了下...实在没找到区别...求各位大大帮忙过目下了= =

Father

int

函数

4 replies • 2015-03-04 23:40:28 +08:00

RecursiveG

Mar 4, 2015

对于找根的函数，else后面没有返回
对于问题二，29行应为father[i]=i;

matrix32767

Mar 4, 2015 via iPad

@RecursiveG
第二个问题确实我愚蠢了。。。

但是第一个，为什么一定要再加一句反回呢？根据我的感觉应该是这样的，比如 n father 的 father 是根。

我getfather（n），发现不是，函数就getfather（father[n]），发现还不是，函数就 getfather(father[father[n]])，最后发现不是就函数输入值father[father[n]]和getfather(father[father[n]])等了，不就return了么。。。为毛我程序跑不起来呢。。。

求指导无比奇妙的递归。。。

bcxx

Mar 4, 2015

@matrix32767 你不 return getfather 的话递归结束的时候怎么跳回上级呢？（你试试用一个栈来模拟递归的过程）

sumhat

Mar 4, 2015

第一问如果有 return，两段代码是等效的，标程在多次查询的情况下效率更高。至于为什么要加 return，请深入学习递归，和并查集没有关系。