图深度优先遍历_编写程序对给定的有向图(不一定连通)进行深度优先遍历,图中包含n个顶点,编号为0至

编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。

输入格式:

输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。

输出格式:

输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。

输入样例1:

3 3
0 1
1 2
0 2

输出样例1:

0 1 2 

输入样例2:

4 4
0 2
0 1
1 2
3 0

输出样例2:

0 1 2 3 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=20005;
vector<int> a[N];
int main(){
    int n,e,x,y;
    cin>>n>>e;
    for(int i=0;i<e;i++){
        cin>>x>>y;
        a[x].push_back(y);
    }
    for(int i=0;i<n;i++){
        sort(a[i].rbegin(),a[i].rend());
    }
    vector<int> v(n,0);
    stack<int> st;
    for(int i=0;i<n;i++){
        st.push(i);
        while(!st.empty()){
            int w=st.top();
            st.pop();
            if(!v[w]){
                cout<<w<<" ";
                v[w]=1;
                int sz=a[w].size();
                for(int j=0;j<sz;j++){
                    if(!v[a[w][j]]) st.push(a[w][j]);
                }
            }
        }
    }
    return 0;
}