DFS
程序员文章站
2022-07-12 10:28:57
...
定义:
DFS,全称Depth First Search,深度优先搜索,一种玄学搜索方法。对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。
思路:
访问一个点a,从a开始对与a有边相连的点进行访问,以此类推。
图解:
我们从点1开始,访问2,然后访问3,从3可以访问6,6后没有点,返回3,访问8,同理,8后面也没有点,不断返回至2,开始访问4,最后将所有点都访问一边。
伪代码:
void dfs(int x){
f[x] = 1;
for (int i = 1;i < = n;i++){
if(a[i][x] && !f[i]) dfs(i);
}
}
眉头一皱,发现这代码好像是真的……
例题:田野上的环
题面:
FJ 让他的N (1 <= N <= 250)只编号为从1到N的奶牛在田地里玩.这些奶牛决定用M条1<=M<=N*(N+1)/2)牛绳将各自连接起来.当然,不会出现一对牛被两条及以上牛绳连接起来.输入告诉你每一条牛绳连接的两只奶牛C1和C2(1 <= c1 <= N; 1 <= c2 <= N; c1 <> c2).
FJ要求奶牛们与1号奶牛相连.现在你要帮助FJ找出所有没有与1号奶牛相连的奶牛.这里的相连既可以是直接的,也可以是间接的(特别的,1号奶牛总是与自己相连).将没有与1号奶牛相连的奶牛的编号升序输出.如果没有这样的牛,输出0。
输入:
第1行:两个用空格分开的整数N,M 第2..M+1行:每一行有两个整数.第i+1行描述的是绳子i连接的两只奶牛的编号,即C1和C2.
输出:
很多行:每一行包含一个整数,意义如题目所说.升序输出.
思路:
DFS例题,只要将从1开始可以访问到的点都标记,最后输出没有标记的点。
真代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1100][1100];
bool f[11000],l = 1;
void init(){
scanf("%d%d",&n,&m);
int x,y;
for(int i = 1;i <= m;i++){
scanf("%d%d",&x,&y);
a[x][y] = 1;
a[y][x] = 1;
}
}
void dfs(int x){
f[x] = 1;
for(int i = 2;i <= n;i++){
if(!f[i] && a[i][x]) dfs(i);
}
}
int main(){
init();
dfs(1);
for(int i = 2;i <= n;i++){
if(!f[i]){
printf("%d\n",i);
l = 0;
}
}
if(l) cout<<0;
return 0;
}