A strongly connected component (SCC) is a subset of vertices in a directed [[graph]] where, for every pair of vertices in the set, there exists a path from one to the other contained entirely within that subset of vertices. Technically, any individual node is a SCC. A cycle in any graph is always an SCC. A **maximal SCC** is an SCC that cannot be made any larger. You cannot add another node and maintain a SCC. There are possibly multiple SCCs within a maximal SCC. Many texts mean maximal SCC when using SCC. To decompose a graph into its maximally strongly connected components is to exhaustively identify all of the maximal SCCs in the graph. Every node will be represented once in this decomposition. The reverse graph $G^T$ has the same set of maximal SCCs and thus the same decomposition as the original. A maximal SCC supergraph is a directed acyclic graph where each node represents one maximal SCC. Use [[depth first search]] to discover the maximal SCCs of a graph. First, list the nodes in descending order of finish time. Then, reverse the graph and conduct depth first search on the first element of the list just created. Remove from the list any nodes discovered during this first depth first search. The nodes discovered during this depth first search is one maximal SCC of the graph. Then move to the next undiscovered node in the list. Continue until the list is empty and all nodes have been discovered. Intuitively, this algorithm is the [[topological sort]] of the maximal SCC supergraph of the graph. This algorithm runs in linear time of the size of the graph.