DFS【东北大学oj数据结构11-2】C++
题面深度优先搜刮（DFS）是一种基于尽大概多地访问相邻顶点战略的图搜刮算法。如果顶点 v 有未搜刮的顶点则递归搜刮直至 v 的最后一条边。在搜刮了 v 的全部边之后，搜刮继承返回到找到 v 时颠末的边。
搜刮从原来的出发点开始，直到找到全部可达的顶点，如果有未发现的顶点，则以编号最小的顶点作为新的出发点继承搜刮。
深度优先搜刮使用以下时间戳标记每个顶点：
d：记载第一次发现v时的时间。
f：记载v的毗邻表被检查完成时的时间。
编写一个步伐，表现基于以下规则的给定有向图 G = (V, E) 的深度优先搜刮相干信息：
此中图 G 以毗邻表的形式给出。每个顶点从 1 到 n 编号。
每个毗邻表的顶点按编号升序排列。
步伐需要输出每个顶点的发现和完成时间。
备注：
在DFS的过程中，如果要访问的顶点有多个，则选择顶点数最小的谁人。
设 1 为第一个要访问的顶点的开始时间。
输入
第一行给出了 G 中的顶点数 n。
接下来的 n 行给出了每个顶点 u 的毗邻表，格式如下：
ukv1v2…vk
u 是顶点的编号，k 是 u 的度数，v1v2…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=timee++;
visited=true;
for(int i=0;i<adj.size();i++)
{
int v=adj;
{
if(!visited)
{
dfs(v,adj);
}
}
}
finish=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.push_back(v);
}
sort(adj.begin(),adj.end());
}
// 初始化数据结构
discovery.assign(n, -1);
finish.assign(n, -1);
visited.assign(n, false);
// 对每个未访问的节点执行DFS
for (int i = 0; i < n; ++i) {
if (!visited) {
dfs(i, adj);
}
}
for(int i=0;i<n;i++)
{
cout << (i + 1) << " " << discovery << " " << finish << endl;
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]