Search
DFS in a directed graph. Using linked lists representation. With additional bonus: Makes a topological ordering when the graph is a DAG.
vector<vector<int> > arc; // edge == arc in a directed graph vector<bool> visited; // needed for DFS vector<int> topSort; // nodes in topological order void DFS_rec( int node ){ visited[node] = true; for( int j = 0; j < arc[node].size(); j++ ) if( !visited[arc[node][j]] ) DFS_rec( arc[node][j] ); topSort.push_back( node ); } void DFS(){ std::fill( visited.begin(), visited.end(), false ); topSort.clear(); for( int start = 0; start < N; start++ ) if( !visited[start] ) DFS_rec( start ); } // DFS close times of nodes not used here, // the order of nodes in the array topSort // defines a topological order. // Because of the main fact: // The nodes in DAG during DFS are being closed // in reverse topological order.