有向图的DFS(c++题解)

题目描述

给定一个有向图(不一定连通)，有N个顶点，M条边，顶点从1..N依次编号，求出字典序最小的深度优先搜索顺序。

输入格式

第1行：2个整数，N（1≤N≤200）和M（2≤M≤5000） 接下来M行，每行2个整数I,J，描述一条边从顶点I指向顶点J

输出格式

仅一行，一个顶点编号序列，表示字典序最小的深度优先搜索序列.顶点之间用一个空格分开

样例

样例输入

复制3 31 21 32 3

样例输出

复制1 2 3

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

_____________________________________________________________________________

#includeusing namespace std;int n,m,u,v;bool vis[1000005];vector a[1000005]; void DFS(int x){vis[x]=true;cout<<x<>n>>m;for(int i=1;i>u>>v;a[u].push_back(v);}for(int i=1;i<=n;i++){sort(a[i].begin(),a[i].end());}for(int i=1;i<=n;i++){if(!vis[i])DFS(i);}}