fork download 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int currentTime = 0;
  6.  
  7. void dfsVisit(vector<vector<int>>& graph, vector<bool>& visited, vector<int>& discovery, vector<int>& finishing, int current) {
  8.     visited[current] = true;
  9.     discovery[current] = ++currentTime;
  10.  
  11.     // Check if current node has an edge to other nodes and visit them if not visited yet
  12.     for (int i = 0; i < graph[current].size(); ++i) {
  13.         if (graph[current][i] == 1 && !visited[i]) {
  14.             cout << "Node " << current << " -> " << i << " - " << currentTime << endl;
  15.             dfsVisit(graph, visited, discovery, finishing, i);
  16.         }
  17.     }
  18.  
  19.     finishing[current] = ++currentTime;
  20. }
  21.  
  22. void dfs(vector<vector<int>>& graph, vector<bool>& visited, vector<int>& discovery, vector<int>& finishing) {
  23.     for (int i = 0; i < graph.size(); ++i) {
  24.         if (!visited[i]) {
  25.             dfsVisit(graph, visited, discovery, finishing, i);
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int n; // number of nodes
  32.     cout << "Enter the number of nodes: " << endl;
  33.     cin >> n;
  34.  
  35.     // defining the adjacency matrix
  36.     vector<vector<int>> graph(n, vector<int>(n, 0));
  37.  
  38.     // creating the adjacency matrix
  39.     cout << "Enter the adjacency matrix (1 if there's an edge, 0 otherwise):\n";
  40.     for (int i = 0; i < n; ++i) {
  41.         for (int j = 0; j < n; ++j)
  42.             cin >> graph[i][j];
  43.     }
  44.  
  45.     vector<bool> visited(n, false);
  46.     vector<int> discovery(n, 0);
  47.     vector<int> finishing(n, 0);
  48.  
  49.     cout << "DFS Traversal Sequence with Discovery and Finishing times: " << endl;
  50.     dfs(graph, visited, discovery, finishing);
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
8
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 1 0 1
0 0 0 0 1 1 0 0
stdout 
Enter the number of nodes: 
Enter the adjacency matrix (1 if there's an edge, 0 otherwise):
DFS Traversal Sequence with Discovery and Finishing times: 
Node 0 -> 3 - 1
Node 0 -> 7 - 3
Node 7 -> 4 - 4
Node 7 -> 5 - 6
https://ideone.com/P4FNi9
language:
C++ (gcc 8.3)
created:
20 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!