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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3663 天前的主题，其中的信息可能已经有所发展或是发生改变。

问题一：
找根的函数，我写的代码：
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 .....程序如下，和标程对比了下...实在没找到区别...求各位大大帮忙过目下了= =

	#include<iostream>
	#include<cstring>
	#include<fstream>
	using namespace std;
	int father[5100];
	string p_save[5100];
	int getfather(int n)
	{
	if(father[n]==n) return n;
	father[n]=getfather(father[n]);
	return father[n];
	}
	int unionfather(int u,int v)
	{
	int fu,fv;
	fu=getfather(u);
	fv=getfather(v);
	if(fu!=fv)
	father[v]=father[u];
	}
	int main()
	{
	int n,m,p;
	int a,b;
	ifstream fin("relation.in");
	fin >>n>>m>>p;
	int i;
	for(i=1;i<=n;i++)
	father[n]=n;
	for(i=1;i<=m;i++)
	{
	fin >>a>>b;
	unionfather(a,b);
	}
	for(i=1;i<=p;i++)
	{
	fin >>a>>b;
	if(father[a]!=father[b])
	p_save[i]="No";
	else p_save[i]="Yes";
	}
	fin.close();
	ofstream fout("relation.out");
	for(i=1;i<=p;i++)
	fout <<p_save[i]<<endl;
	fout.close();
	return 0;
	}

view raw 1034.cpp hosted with ❤ by GitHub

Father

int

函数

4 条回复 • 2015-03-04 23:40:28 +08:00

RecursiveG

2015-03-04 23:03:17 +08:00

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

matrix32767

2015-03-04 23:29:27 +08:00 via iPad

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

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

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

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

bcxx

2015-03-04 23:32:22 +08:00

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

sumhat

2015-03-04 23:40:28 +08:00

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