The KosarajuSharirSCC class represents a data type for determining the strong components in a digraph. The Id operation determines in which strong component a given vertex lies; the AreStronglyConnected operation determines whether two vertices are in the same strong component; and the Count operation determines the number of strong components. The Component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.

This implementation uses the Kosaraju-Sharir algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the Id, Count, and AreStronglyConnected operations take constant time. For alternate implementations of the same API, see and .