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.

- 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.
- Mark the source vertex as discovered and set its arrival time to 0 and increment the time by 1.
- 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 vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int N) { // resize the vector to N elements of type vector<int> adjList.resize(N); // add edges to the directed graph for (auto &edge: edges) adjList[edge.src].push_back(edge.dest); } }; // 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; for (int i : graph.adjList[v]) 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.*

## One comment