Strongly connected component

Several algorithms based on depth-first search compute strongly connected components in linear time.

Previous linear-time algorithms are based on depth-first search which is generally considered hard to parallelize.

The two queries partition the vertex set into 4 subsets: vertices reached by both, either one, or none of the searches.

Blelloch et al.[8] in 2016 shows that if the reachability queries are applied in a random order, the cost bound of O(n log n) still holds.

The overall span of this algorithm is log2 n reachability queries, which is probably the optimal parallelism that can be achieved using the reachability-based approach.

Algorithms for finding strongly connected components may be used to solve 2-satisfiability problems (systems of Boolean variables with constraints on the values of pairs of variables): as Aspvall, Plass & Tarjan (1979) showed, a 2-satisfiability instance is unsatisfiable if and only if there is a variable v such that v and its negation are both contained in the same strongly connected component of the implication graph of the instance.

Graph with strongly connected components marked
The yellow directed acyclic graph is the condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.