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 

代码 

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <stack>
using namespace std;
 
vector<int> discovery;
vector<int> finish;
vector<bool> visited;
int timee=1;
void dfs(int u,const vector<vector<int> >& adj)
{
    discovery[u]=timee++;
    visited[u]=true;
    for(int i=0;i<adj[u].size();i++)
    {
        int v=adj[u][i];
        {
            if(!visited[v])
            {
                dfs(v,adj);
            }
        }
    }
    finish[u]=timee++;
}
int main() {
    int n;
    cin >> n;
 
    vector<vector<int>> adj(n);
    for(int i=0;i<n;i++)
    {
        int u,k;
        cin>>u>>k;
        u--;
        for(int j=0;j<k;j++)
        {
            int v;
            cin>>v;
            v--;
            adj[u].push_back(v);
        }
        sort(adj[u].begin(),adj[u].end());
    }
 
    // 初始化数据结构
    discovery.assign(n, -1);
    finish.assign(n, -1);
    visited.assign(n, false);
 
    // 对每个未访问的节点执行DFS
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, adj);
        }
    }
 
    for(int i=0;i<n;i++)
    {
        cout << (i + 1) << " " << discovery[i] << " " << finish[i] << endl;
    }
 
 
    return 0;
}