社区讨论
求助,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 条回复,欢迎继续交流。
正在加载回复...