并查集新人求助,家谱那题,为什么找不到祖先呢?
  • 板块P2814 家谱
  • 楼主ShunpowerSHUN理成张
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/4/14 20:43
  • 上次更新2023/11/5 00:32:59
查看原帖
并查集新人求助,家谱那题,为什么找不到祖先呢?
399150
ShunpowerSHUN理成张楼主2021/4/14 20:43

问题:

1.部分人查找的时候老是找不到祖先(也就是返回值为空,我认为是返回到了一个空MAP上)

2.我把录入父亲的地方(也就是判断是不是有父之人)给改了,不知道是不是改的问题。

3.我个人认为find的地方顺手路径压缩应该没有问题。

贴c++代码求debug:

#include <bits/stdc++.h>
using namespace std;
map<string, string> f;
string find(string x){
	if(x!=f[x]){
    	f[x]=find(f[x]);
	}
  	return f[x];
}
int main(){
	char fuhao;
	for(;;){
		string a,fa;
		cin>>fuhao;
		if(fuhao=='$'){
			break;
		}
		if(fuhao=='#'){
			cin>>fa;
			if(f[fa]==""){
				f[fa]=fa;
			}
		}
		if(fuhao=='+'){
			cin>>a;
			f[a]=fa;
		}
		if(fuhao=='?'){
			cin>>a;
			cout<<a<<" "<<find(a)<<endl;
		}
	}
	return 0;

2021/4/14 20:43
加载中...