DFS【东北大学oj数据结构11-2】C++

题面

深度优先搜刮（DFS）是一种基于尽大概多地访问相邻顶点战略的图搜刮算法。如果顶点 v 有未搜刮的顶点则递归搜刮直至 v 的最后一条边。在搜刮了 v 的全部边之后，搜刮继承返回到找到 v 时颠末的边。
搜刮从原来的出发点开始，直到找到全部可达的顶点，如果有未发现的顶点，则以编号最小的顶点作为新的出发点继承搜刮。
深度优先搜刮使用以下时间戳标记每个顶点：
d[v]：记载第一次发现v时的时间。
f[v]：记载v的毗邻表被检查完成时的时间。
编写一个步伐，表现基于以下规则的给定有向图 G = (V, E) 的深度优先搜刮相干信息：
此中图 G 以毗邻表的形式给出。每个顶点从 1 到 n 编号。
每个毗邻表的顶点按编号升序排列。
步伐需要输出每个顶点的发现和完成时间。
备注：
在DFS的过程中，如果要访问的顶点有多个，则选择顶点数最小的谁人。
设 1 为第一个要访问的顶点的开始时间。
输入

第一行给出了 G 中的顶点数 n。
接下来的 n 行给出了每个顶点 u 的毗邻表，格式如下：
ukv1​v2​…vk​
u 是顶点的编号，k 是 u 的度数，v1​v2​…vk​ 是与 u 相邻的顶点的编号。
输出

输出 n 行，在第 i 行上输出第 i 个顶点的 id、d、f以空格分隔。
id是顶点的编号，d是顶点的发现时间，f是顶点的完成时间。
按顶点编号从小到大输出。
约束

• 1≤n≤100
  

输入样例
   4
1 1 2
2 1 4
3 0
4 1 3
  输出样例
   1 1 8
2 2 7
3 4 5
4 3 6 
  代码 

1. #include <iostream>
2. #include <vector>
3. #include <iomanip>
4. #include <algorithm>
5. #include <stack>
6. using namespace std;
8. vector<int> discovery;
9. vector<int> finish;
10. vector<bool> visited;
11. int timee=1;
12. void dfs(int u,const vector<vector<int> >& adj)
13. {
14.     discovery[u]=timee++;
15.     visited[u]=true;
16.     for(int i=0;i<adj[u].size();i++)
17.     {
18.         int v=adj[u][i];
19.         {
20.             if(!visited[v])
21.             {
22.                 dfs(v,adj);
23.             }
24.         }
25.     }
26.     finish[u]=timee++;
27. }
28. int main() {
29.     int n;
30.     cin >> n;
32.     vector<vector<int>> adj(n);
33.     for(int i=0;i<n;i++)
34.     {
35.         int u,k;
36.         cin>>u>>k;
37.         u--;
38.         for(int j=0;j<k;j++)
39.         {
40.             int v;
41.             cin>>v;
42.             v--;
43.             adj[u].push_back(v);
44.         }
45.         sort(adj[u].begin(),adj[u].end());
46.     }
48.     // 初始化数据结构
49.     discovery.assign(n, -1);
50.     finish.assign(n, -1);
51.     visited.assign(n, false);
53.     // 对每个未访问的节点执行DFS
54.     for (int i = 0; i < n; ++i) {
55.         if (!visited[i]) {
56.             dfs(i, adj);
57.         }
58.     }
60.     for(int i=0;i<n;i++)
61.     {
62.         cout << (i + 1) << " " << discovery[i] << " " << finish[i] << endl;
63.     }
66.     return 0;
67. }

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。