编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含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
思路：
使用从《啊哈算法》中学到的建立一个20000*20000的数组来当邻接矩阵，是非常浪费空间和时间的，在测试的时候是过不去的，那么《数据结构》上还有一种和邻接矩阵功能类似的结构叫邻接表，而我们用C++的Vector即可实现
实现代码：
#include<iostream>#include<vector>#include<algorithm>usingnamespacestd; //建立表头结点表 vector<int>adjacency[20000]; intbook[20000]; voiddfs(intcur){ cout<<cur<<" "; book[cur]=1; //遍历链表中的结点 intlength=adjacency[cur].size(); for(inti=0;i<length;i++){ if(book[adjacency[cur][i]]==0){ dfs(adjacency[cur][i]); } } } intmain(){ intvertex,edge,vertex1,vertex2; cin>>vertex>>edge; //输入边 for(inti=0;i<edge;i++){ cin>>vertex1>>vertex2; adjacency[vertex1].push_back(vertex2); } //给邻接表的每个链表的结点排序 for(inti=0;i<vertex;i++){ sort(adjacency[i].begin(),adjacency[i].end()); } //遍历每个结点 for(inti=0;i<vertex;i++){ if(book[i]==0){ dfs(i); } } return0; }
![[Atcoder ABC222] F - Expensive Expense | 妙用树的直径 | Dijkstra](https://ucc.alicdn.com/pic/developer-ecology/de3deaf60a8c47e19f061114e6c4be7a.png?x-oss-process=image/resize,h_160,m_lfit)