00001 #ifndef SCC_H 00002 #define SCC_H 00003 00004 /* 00005 This implements Tarjan's linear-time algorithm for finding the maximal 00006 strongly connected components. It takes time proportional to the sum 00007 of the number of vertices and arcs. 00008 00009 Instantiate class SCC with a graph represented as a vector of vectors, 00010 where graph[i] is the vector of successors of vertex i. 00011 00012 Method get_result() returns a vector of strongly connected components, 00013 each of which is a vector of vertices (ints). 00014 This is a partitioning of all vertices where each SCC is a maximal subset 00015 such that each node in an SCC is reachable from all other nodes in the SCC. 00016 Note that the derived graph where each SCC is a single "supernode" is 00017 necessarily acyclic. The SCCs returned by get_result() are in a topological 00018 sort order with regard to this derived DAG. 00019 */ 00020 00021 #include <vector> 00022 using namespace std; 00023 00024 class SCC { 00025 const vector<vector<int> > &graph; 00026 00027 // The following three are indexed by vertex number. 00028 vector<int> dfs_numbers; 00029 vector<int> dfs_minima; 00030 vector<int> stack_indices; 00031 00032 vector<int> stack; // This is indexed by the level of recursion. 00033 vector<vector<int> > sccs; 00034 00035 int current_dfs_number; 00036 00037 void dfs(int vertex); 00038 public: 00039 SCC(const vector<vector<int> > &theGraph) : graph(theGraph) {} 00040 vector<vector<int> > get_result(); 00041 }; 00042 #endif