图的遍历 - DFS - 邻接表
作者:
Yotu
,
2024-08-19 18:12:03
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N = 10000001;
int st[N];
//邻接表结构,数组+链表
struct node{
int id;
node* next;
node(int _id) : id(_id),next(NULL){}
}*head[N];
//邻接表添加节点
void add(int a,int b){ // 头插法
auto p = new node(b);
p->next = head[a]; // 顺序不能乱
head[a] = p;
}
void dfs(int u){
st[u] = true;
cout << u << ' ';
for(auto p = head[u] ; p ; p=p->next){
if(!st[p->id]) dfs(p->id);
}
}
int main(){
cin >> n, m;
while(m--){
int a,b;
cin >> a >> b;
add(a,b);
}
for(int i = 1 ; i <= n; i++){
if(!st[i]) dfs(i);
}
return 0;
}