#include <bits/stdc++.h>
using namespace std;
void dfsVisit (vector<vector<int>>& graph, vector<bool>& visited, int current,vector<int>& discTime,vector<int>& finishTime,int &t,int arr[],int &k){
visited [current] = true;
arr[k]=current;
k++;
discTime[current]=++t;
for(int i=0; i<graph.size(); i++){
if(graph[current][i]==1 && visited[i]==false)
dfsVisit(graph, visited, i,discTime,finishTime,t,arr,k);
}
finishTime[current]=++t;
}
void dfs(vector<vector<int>>& graph, vector<bool>& visited,vector<int>& discTime,vector<int>& finishTime,int &t,int arr[],int &k){
for(int i=0; i<graph.size(); i++){
if(visited[i]==false)
dfsVisit(graph, visited, i,discTime,finishTime,t,arr,k);
}
}
int main() {
int n;
cout << "Enter the number of nodes: " << endl;
cin >> n;
// defining the adjacency matrix
vector<vector<int>> graph (n,vector<int>(n,0));
// creating the adjacency matrix
for(int i=0; i<n; i++){
for(int j=0; j<n; j++)
cin >> graph[i][j];
}
vector<bool> visited (n, false);
vector<int> discTime (n, 0);
vector<int> finishTime (n, 0);
int t=0,k=0;
int arr[n];
cout << "DFS Traversal Sequence: " << endl;
dfs(graph,visited,discTime,finishTime,t,arr,k);
for(int i=0;i<n;i++){
cout<<"Node: "<< arr[i]<<"-->"<<discTime[arr[i]]<<"--"<<finishTime[arr[i]]<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIGRmc1Zpc2l0ICh2ZWN0b3I8dmVjdG9yPGludD4+JiBncmFwaCwgdmVjdG9yPGJvb2w+JiB2aXNpdGVkLCBpbnQgY3VycmVudCx2ZWN0b3I8aW50PiYgZGlzY1RpbWUsdmVjdG9yPGludD4mIGZpbmlzaFRpbWUsaW50ICZ0LGludCBhcnJbXSxpbnQgJmspewoKCXZpc2l0ZWQgW2N1cnJlbnRdID0gdHJ1ZTsKCWFycltrXT1jdXJyZW50OwoJaysrOwoJZGlzY1RpbWVbY3VycmVudF09Kyt0OwogICAgZm9yKGludCBpPTA7IGk8Z3JhcGguc2l6ZSgpOyBpKyspewoJCWlmKGdyYXBoW2N1cnJlbnRdW2ldPT0xICYmIHZpc2l0ZWRbaV09PWZhbHNlKQoJCQlkZnNWaXNpdChncmFwaCwgdmlzaXRlZCwgaSxkaXNjVGltZSxmaW5pc2hUaW1lLHQsYXJyLGspOwoJfQoJZmluaXNoVGltZVtjdXJyZW50XT0rK3Q7Cn0KCnZvaWQgZGZzKHZlY3Rvcjx2ZWN0b3I8aW50Pj4mIGdyYXBoLCB2ZWN0b3I8Ym9vbD4mIHZpc2l0ZWQsdmVjdG9yPGludD4mIGRpc2NUaW1lLHZlY3RvcjxpbnQ+JiBmaW5pc2hUaW1lLGludCAmdCxpbnQgYXJyW10saW50ICZrKXsKCWZvcihpbnQgaT0wOyBpPGdyYXBoLnNpemUoKTsgaSsrKXsKCQlpZih2aXNpdGVkW2ldPT1mYWxzZSkKCQkJZGZzVmlzaXQoZ3JhcGgsIHZpc2l0ZWQsIGksZGlzY1RpbWUsZmluaXNoVGltZSx0LGFycixrKTsKCX0KfQoKaW50IG1haW4oKSB7CgoJaW50IG47IAoJY291dCA8PCAiRW50ZXIgdGhlIG51bWJlciBvZiBub2RlczogIiA8PCBlbmRsOwoJY2luID4+IG47CgkvLyBkZWZpbmluZyB0aGUgYWRqYWNlbmN5IG1hdHJpeAoKCXZlY3Rvcjx2ZWN0b3I8aW50Pj4gZ3JhcGggKG4sdmVjdG9yPGludD4obiwwKSk7CgoJLy8gY3JlYXRpbmcgdGhlIGFkamFjZW5jeSBtYXRyaXgKCWZvcihpbnQgaT0wOyBpPG47IGkrKyl7CgkJZm9yKGludCBqPTA7IGo8bjsgaisrKQoJCQljaW4gPj4gZ3JhcGhbaV1bal07Cgl9Cgl2ZWN0b3I8Ym9vbD4gdmlzaXRlZCAobiwgZmFsc2UpOwoJdmVjdG9yPGludD4gZGlzY1RpbWUgKG4sIDApOwoJdmVjdG9yPGludD4gZmluaXNoVGltZSAobiwgMCk7CglpbnQgdD0wLGs9MDsKCWludCBhcnJbbl07CgoJY291dCA8PCAiREZTIFRyYXZlcnNhbCBTZXF1ZW5jZTogIiA8PCBlbmRsOwoJZGZzKGdyYXBoLHZpc2l0ZWQsZGlzY1RpbWUsZmluaXNoVGltZSx0LGFycixrKTsKCWZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAgIGNvdXQ8PCJOb2RlOiAiPDwgYXJyW2ldPDwiLS0+Ijw8ZGlzY1RpbWVbYXJyW2ldXTw8Ii0tIjw8ZmluaXNoVGltZVthcnJbaV1dPDxlbmRsOwoJfQoJcmV0dXJuIDA7Cn0K