Editing Strongly connected component (section)

==Applications==
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 {{harvtxt|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.<ref>{{citation
 | last1 = Aspvall | first1 = Bengt
 | last2 = Plass | first2 = Michael F.
 | author-link3 = Robert Tarjan | last3 = Tarjan | first3 = Robert E.
 | title = A linear-time algorithm for testing the truth of certain quantified boolean formulas
 | journal = Information Processing Letters
 | volume = 8 | issue = 3 | pages = 121–123 | year = 1979
 | doi = 10.1016/0020-0190(79)90002-4}}.</ref>

Strongly connected components are also used to compute the [[Dulmage–Mendelsohn decomposition]], a classification of the edges of a [[bipartite graph]], according to whether or not they can be part of a [[perfect matching]] in the graph.<ref>{{citation |title=Coverings of bipartite graphs |first1=A. L. |last1=Dulmage |author-link2=Nathan Mendelsohn |first2=N. S. |last2=Mendelsohn |name-list-style=amp |journal=Can. J. Math. |year=1958 |volume=10 |pages=517–534 |doi=10.4153/cjm-1958-052-0|s2cid=123363425 |doi-access=free }}.</ref>