Tarjan

template<class G> class Tarjan

Public Functions

inline Tarjan(const G &graph)

inline int sccCount() const: Returns the number of strongly connected components of the graph.

inline const std::vector<std::vector<int>> &sccs() const: Returns a vector containing the strongly connected components of the graph.

inline int scc(const int v) const: Returns the ID of the strongly connected component containing a given vertex.

Private Functions

int findSccs(const G &g, const int vertex): Returns the lowest id of a vertex directly accessible from the subtree.

Private Members

const int NOT_VISITED = -2

const int IN_STACK = -1

std::vector<int> m_states

int m_nextID

std::vector<int> m_ids

std::stack<int> pendingVertice

std::vector<std::vector<int>> m_sccs