SCCStrongly Connected Component,强连通分量)是 有向图 中极大的 强连通 子图,其中任意两个顶点都可以沿有向边互相到达。

它把有向图里“彼此可达”的顶点归成一组。每个顶点恰好属于一个 SCC;如果把每个 SCC 看成一个点,跨分量的边会形成无环的分量图,这个过程通常叫 缩点

常见求法包括 Tarjan 算法Kosaraju 算法,二者都可以在线性时间内完成。详细推导和代码实现见 强连通分量