強連結成分分解

強連結成分分解(Strongly-Connected-Components, SCC)をメモっておきます。 強連結成分というのは、有向グラフにおいて、そのグループに含まれている点は、どの点u,vをとってもお互いに行き来出来るというものです。例えばサイクルなどは明らかに強連結成分ですし、孤立点のない無向グラフなども当然そうなります。 与え…