あらすじ

有向グラフの頂点は、「互いに行き来できる」という（同値）関係によってグループ分けできます。これを 強連結成分 と言います。

頂点数 \(N\) 辺数 \(M\) の有向グラフの強連結成分をすべて求めることは、 強連結成分分解 というアルゴリズムによって時間計算量 \(O(N+M)\) で達成出来ます。

強連結成分を縮約して \(1\) つの頂点とみなした有向グラフ（自己ループは消す）は DAG（非巡回有向グラフ）となります。

今回の問題では有向グラフの強連結成分を縮約して DAG 上の問題に置き換えることができ、問題の見通しが良くなります。

考察

\(N\) 頂点 \(M\) 辺の有向グラフを次のように作ります。

• \(i\) 番目の辺は、\(a_i \to b_i\) に辺を張る

また、任意の頂点 \(i \ ( 1 \le i \le N)\) に対して、 \(i\) から到達可能な頂点全体の集合を \(R(i)\) とします。そうすると、問題は次のように言い換えられます：

【問題】 \(\{1, 2, \cdots, N\}\) の部分集合 \(S = \{S_1, S_2, \cdots, S_k\}\) を、

\[R(S_1) \cup R(S_2) \cup \cdots \cup R(S_k) = \{1, 2, \cdots, N\}\]

を満たすように選ぶとき、 \(S\) の要素数 \(k\) の最小値を求めよ。

ここからは、言い換えた後の問題に注目します。もし、頂点 \(a, b \ (1 \le a, b \le N)\) について、 \(a\) から \(b\)、 \(b\) から \(a\) がともに到達可能であるなら、必ず \(R(a) = R(b)\) になります。

\(R(a) = R(b)\) の証明

一般に、到達可能性には推移性があります。 \(x\) から \(y\)、 \(y\) から \(z\) に到達可能なら、 \(x\) から \(y\) を経由して \(z\) に到達できるので、 \(x\) から \(z\) に到達可能です。

\(a\) から \(b\) には到達可能なので、 \(b\) から到達可能な任意の頂点 \(x\) に対して、 \(a\) から \(x\) に到達可能です。 これは \(x \in R(b) \Rightarrow x \in R(a)\) を表します。よって、 \(R(b) \subset R(a)\) が成り立ちます。

上の議論において \(a, b\) を交換すれば \(R(a) \subset R(b)\) も言えるため、 \(R(a) = R(b)\) が示されました。

よって、 \(\{1, 2, \cdots, N\}\) の部分集合において \(a, b\) をともに選ぶのは最適ではありません。

有向グラフは「互いに行き来できる」という（同値）関係によってグループ分けできます。これを 強連結成分 と言います。上の議論により、同じ強連結成分に属する頂点は、どれを選んでも、そこから到達可能な頂点の集合はすべて同じになります。そして、\(\{1,2, \cdots, N\}\) の部分集合 \(S\) において、同じ強連結成分に属する \(2\) 個以上の頂点を選ぶのは最適ではありません。

強連結成分分解 というアルゴリズムによって強連結成分をすべて求めることができます。強連結成分を \(1\) 個の頂点とみなしてグラフを縮約すると、そのグラフは DAG（非巡回有向グラフ）になります。よって、この問題は DAG 上の同じ問題に帰着されます。

DAG 帰着後

有向グラフが DAG であったときの【問題】を考えます。

入次数が \(0\) の頂点 \(x\) に注目すると、\(x\) に到達可能である頂点は \(x\) だけであるので、 \(x\) は必ず \(S\) に属する必要があります。よって、条件を満たす \(S\) において、\(S\) は必ず「入次数が \(0\) の頂点全体の集合」を含みます。

実は、 \(S\) を入次数が \(0\) の頂点全体の集合とすると、問題の条件を満たすことが示されます。

証明

感覚的には、次のようにして分かります。「自分に繋がっている辺を逆にたどると、最終的には必ず入次数 \(0\) の頂点にぶつかるが、その頂点から自分には到達可能である。よって OK。」以下では、これを頑張って表します。

\(S = \{S_1, S_2, \cdots, S_k\}\) とし、 \(R(S) = R(S_1) \cup R(S_2) \cup \cdots \cup R(S_k)\) とします。

\(S = \{S_1, S_2, \cdots, S_k\}\) を入次数が \(0\) の頂点全体の集合とすると、 \(R(S) = \{1, 2, \cdots, N\}\) であることを示します。

\(R(S) \subset \{1, 2, \cdots, N\}\) は明らかなので、 \(R_S \supset \{1, 2, \cdots, N\}\) 、すなわち、任意の頂点 \(y_0\) について \(y_0 \in R(S)\) であることを示せばよいです。

\(y_0\) の入次数が \(0\) ならば \(y_0 \in S \subset R(S)\) なので OK です。 \(y_0\) の入次数が \(1\) 以上なら、頂点 \(y_1\) であって、 \(y_1 \to y_0\) に辺が張られているものが存在します。

その頂点 \(y_1\) について、 \(y_1\) の入次数が \(0\) ならば、 \(y_1 \in S\) かつ \(y_1\) から \(y_0\) に到達可能なので、 \(y_0 \subset R(S)\) となり、 OK です。 \(y_1\) の入次数が \(1\) 以上なら、頂点 \(y_2\) であって、 \(y_2 \to y_1\) に辺が張られているものが存在します。

これを \(y_2, y_3, \cdots\) と繰り返すと、グラフが DAG であり頂点数が有限なので、 \(y_l \ (l \ge 0)\) が存在して、 \(y_l\) の入次数が \(0\) かつ、 \(y_l\) から \(y_0\) に到達可能であるものが存在します。いま、入次数が \(0\) の頂点はすべて \(S\) に属しているので、 \(y_0 \in R(S)\) となります。

したがって、 \(R(S) \supset \{1, 2, \cdots, N\}\) が示されました。

「入次数が \(0\) の頂点全体の集合」は問題の条件を満たす最小の集合です。よって、問題の答えは「入次数が \(0\) である頂点の個数」となります。

まとめ

次の \(2\) ステップで解けます。

1. 強連結成分分解をする。
2. 強連結成分を縮約すると、DAG になる。その DAG において、入次数が \(0\) の頂点の個数が答えである。

時間・空間計算量はともに \(O(N+M)\) です。

実装例(C++)