@[smile_jyc](/user/1246532) 你广搜怎么用深搜的架构
by int_stl @ 2024-04-19 20:23:16
@[smile_jyc](/user/1246532)
一边广搜，一边深搜？？？
by xpg007 @ 2024-04-19 20:39:16
@[smile_jyc](/user/1246532) ```cpp
#include<bits/stdc++.h>
using namespace std;
long long a[1001][1001],visd[100000],visb[100000];
long long n,m;
long long dfs(long long bt){
if(visd[bt]) return 0;
if(bt==1){
cout<<bt;
}else {
cout<<"-"<<bt;
}
visd[bt]=1;
for(int j=1;j<=n;j++){
if(visd[j]) continue;
if(a[bt][j]==1){
dfs(j);
}
}
return 0;
}
long long bfs(long long bt){
queue<int> q;
q.push(bt);
visb[bt] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
if(u == 1) cout << u;
else cout << "-" << u;
for(int i=1;i<=n;i++){
if(visb[i]) continue;
if(a[u][i] == 1){
visb[i] = 1;
q.push(i);
}
}
}
return 0;
}
int main(){
cin>>n>>m;
long long x,y;
for(int i=0;i<m;i++){
cin>>x>>y;
a[x][y]=a[y][x]=1;
}
dfs(1);
for(int i=1;i<=n;i++){
if(visd[i]==0){
if(i==1){
cout<<i;
}else{
cout<<"-"<<i;
}
}
}
cout<<endl;
bfs(1);
for(int i=1;i<=n;i++){
if(visb[i] == 0){
if(i==1){
cout<<i;
}else{
cout<<"-"<<i;
}
}
}
return 0;
}
```
by Li_Yichen @ 2024-04-19 20:46:06
@[smile_jyc](/user/1246532)
```cpp
#include<bits/stdc++.h>
using namespace std;
long long a[1001][1001],visd[100000],visb[100000];
long long n,m;
long long dfs(long long bt){
if(visd[bt]) return 0;
if(bt==1){
cout<<bt;
}else {
cout<<"-"<<bt;
}
visd[bt]=1;
for(int j=1;j<=n;j++){
if(visd[j]) continue;
if(a[bt][j]==1){
dfs(j);
}
}
return 0;
}
long long bfs(long long bt){
queue<int> q;
q.push(bt);
visb[bt] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
if(u == 1) cout << u;
else cout << "-" << u;
for(int i=1;i<=n;i++){
if(visb[i]) continue;
if(a[u][i] == 1){
visb[i] = 1;
q.push(i);
}
}
}
return 0;
}
int main(){
cin>>n>>m;
long long x,y;
for(int i=0;i<m;i++){
cin>>x>>y;
a[x][y]=a[y][x]=1;
}
dfs(1);
for(int i=1;i<=n;i++){
if(visd[i]==0){
if(i==1){
cout<<i;
}else{
cout<<"-"<<i;
}
}
}
cout<<endl;
bfs(1);
for(int i=1;i<=n;i++){
if(visb[i] == 0){
if(i==1){
cout<<i;
}else{
cout<<"-"<<i;
}
}
}
return 0;
}
```
by Li_Yichen @ 2024-04-19 20:46:35
@[smile_jyc](/user/1246532) 有几个问题。第一个，也是最大的问题，bfs用的是队列而不是递归。第二个，dfs和bfs搜索下一个点的时候要注意看一下有没有被访问过，即vis数组，否则有可能会循环下去。一开始发的 Latex 炸了，不要在意，$(*/ω＼*)$
by Li_Yichen @ 2024-04-19 20:48:54
@[Li_Yichen](/user/930325) 谢谢
by smile_jyc @ 2024-04-19 20:52:42