社区讨论

求助,DFS错,BFS还是错(DFS和AC代码几乎一模一样,哪错了)

P5908猫猫和企鹅参与者 2已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo8mi8xk
此快照首次捕获于
2023/10/27 21:02
2 年前
此快照最后确认于
2023/10/27 21:02
2 年前
查看原帖

DFS全WA代码

CPP
#include <stdio.h>
#include <vector>
using namespace std;
vector <int> e[100001];
int n,d,ans=0;
void dfs(int p,int fa,int bs)
{
	if(bs==d) return ;
	for(int i=0;i<e[p].size();i++)
	{
		if(e[p][i]==fa) continue;
		dfs(e[p][i],p,bs+1);
		ans++;
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&d);
	int u,v;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(u);
		e[v].push_back(v);
	}
	dfs(1,0,0);
	printf("%d\n",ans);
	return 0;
}

DFS AC代码

CPP
#include <bits/stdc++.h>
using namespace std;
vector <int> e[200005];
int n,u,v,d,ans=0;
void dfs(int u,int fa,int dep)
{
	if(dep==d) return;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa) continue;
		dfs(v,u,dep+1);
		ans++;
	}
	return;
}
int main()
{
	cin>>n>>d;
	for(int i=1;i<=n-1;i++)
	{
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0,0);
	cout<<ans<<endl;
	return 0;
}

BFS全WA代码

CPP
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
struct zb
{
	int p,s,fa;
};
vector <int> e[200001];
queue <zb> l;
void push(int p,int fa,int s)
{
	l.push((zb){p,fa,s});
	return ;
}
int n,d,ans=0,x=0;
void bfs()
{
	push(1,0,0);
	while(x<=d)
	{
		int p=l.front().p;
		int fa=l.front().fa;
		int s=l.front().s;
		l.pop();
		for(int i=0;i<e[p].size();i++)
		{
			if(e[p][i]==fa) continue;
			push(e[p][i],p,s+1);
			ans=s+1;
		}
		x++;
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&d);
	int u,v;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(u);
		e[v].push_back(v);
	}
	bfs();
	printf("%d\n",ans);
	return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...