# Arrival and Departure time.

You are given a directed graph. You need to find the arrival and departure time of all the vertices in the graph. Arrival time is the at which a vertex was explored the first time in the DFS traversal of the graph and departure time is the time at which we have explored all the neighboring vertices of the vertex and are now ready to backtrack.

Consider the below graph.

The arrival and departure time of the vertices are as follows –

Vertex 0 (0, 11)
Vertex 1 (1, 2)
Vertex 2 (3, 10)
Vertex 3 (4, 7)
Vertex 4 (8, 9)
Vertex 5 (5, 6)
Vertex 6 (12, 15)
Vertex 7 (13, 14)

Algorithm:

We can solve the problem using simple DFS traversal.

1. We keep two lists arrival and departure to store the arrival and departure time of the vertices and a variable time to keep track of the current time.
2. Mark the source vertex as discovered and set its arrival time to 0 and increment the time by 1.
3. For all the neighboring vertices of the current vertex, if they have not been previously discovered, recur for those vertices and while backtracking, set their departure times as well.
```#include <bits/stdc++.h>
using namespace std;

// data structure to store graph edges
struct Edge {
int src, dest;
};

// class to represent a graph object
class Graph
{
public:
// construct a vector of vectors to represent an adjacency list

// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to N elements of type vector<int>

// add edges to the directed graph
for (auto &edge: edges)
}
};

// Function to perform DFS Traversal
void DFS(Graph const &graph, int v, vector<bool> &discovered,
vector<int> &arrival, vector<int> &departure, int &time)
{
// set arrival time of vertex v
arrival[v] = ++time;

// mark vertex as discovered
discovered[v] = true;

if (!discovered[i])
DFS(graph, i, discovered, arrival, departure, time);

// set departure time of vertex v
departure[v] = ++time;
}

// main function
int main()
{
// vector of graph edges as per above diagram
vector<Edge> edges = {
{0, 1}, {0, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 5},
{4, 5}, {6, 7}
};

// Number of nodes in the graph
int N = 8;

// create a graph from given edges
Graph graph(edges, N);

// vector to store arrival time of vertex
vector<int> arrival(N);

// vector to store departure time of vertex
vector<int> departure(N);

// Mark all the vertices as not discovered
vector<bool> discovered(N);
int time = -1;

// Do DFS traversal from all undiscovered nodes to
// cover all unconnected components of graph
for (int i = 0; i < N; i++)
if (!discovered[i])
DFS(graph, i, discovered, arrival, departure, time);

// print arrival and departure time of each
// vertex in DFS
for (int i = 0; i < N; i++) {
cout << "Vertex " << i << " (" << arrival[i]
<< ", " << departure[i] << ")" << endl;
}

return 0;
}```

Also check out another popular interview question Print all paths from root to leaf in a tree.