图的遍历 - DFS - 栈(非递归)
作者:
Yotu
,
2024-08-19 18:40:28
,
所有人可见
,
阅读 1
#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 StackDfs(int i){
stack<int> s;
s.push(i);
st[i] = true;
while(s.size()){
int t = s.top();
cout << t <<' ';
s.pop();
for(auto p = head[t]; p ; p = p->next){
if(!st[p->id]){
s.push(p->id);
st[p->id] = true;
}
}
}
}
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]) StackDfs(i);
}
return 0;
}