这是一个创建于 3543 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题一：
找根的函数，我写的代码：
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 .....程序如下，和标程对比了下...实在没找到区别...求各位大大帮忙过目下了= =
找根的函数，我写的代码：
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 .....程序如下，和标程对比了下...实在没找到区别...求各位大大帮忙过目下了= =
 |
1
RecursiveG 2015-03-04 23:03:17 +08:00
对于找根的函数，else后面没有返回
对于问题二，29行应为father[i]=i; |
 |
2
matrix32767 OP @RecursiveG
第二个问题确实我愚蠢了。。。 但是第一个，为什么一定要再加一句反回呢？根据我的感觉应该是这样的，比如 n father 的 father 是根。 我getfather（n），发现不是，函数就getfather（father[n]），发现还不是，函数就 getfather(father[father[n]])，最后发现不是就函数输入值father[father[n]]和getfather(father[father[n]])等了，不就return了么。。。为毛我程序跑不起来呢。。。 求指导无比奇妙的递归。。。 |
 |
3
bcxx 2015-03-04 23:32:22 +08:00
@matrix32767 你不 return getfather 的话递归结束的时候怎么跳回上级呢？（你试试用一个栈来模拟递归的过程）
|
 |
4
sumhat 2015-03-04 23:40:28 +08:00
第一问如果有 return，两段代码是等效的，标程在多次查询的情况下效率更高。至于为什么要加 return，请深入学习递归，和并查集没有关系。
|
Select Language