3월, 2019의 게시물 표시

Iterative DFS on the graph with post-visit ordering

Recently, I'm studying about SCC(Strongly Connected Component) related subjects. Kosaraju's algorithm and Tarjan's algorithm are two representative algorithm to calculate SCC of graph. Kosaraju's algorithm requires post-visit order list of DFS. With recursive DFS, it's straightforward. But conventional iterative DFS algorithm can't calculate post-visit order. Since that it doesn't store any information about vertices that previously visited. Although I've googled several hrs to find nice implementation, I failed it. So, I implemented with additional depth stack and parent array. If you have idea for any furture simplification or optimization, please mail me! #include <iostream> #include <vector> #include <algorithm> #include <stack> using namespace std; int main() { int N; // Number of vertices int M; // Number of edges vector<vector<int>> graph; // Adjacency list of graph stack<int>