Solicitation of Murder

解説

囚人を頂点、関係 $(A_i,B_i)$ を有向辺 $A_i \to B_i$ とする有向グラフを考えます。

このグラフを強連結成分分解することを考えます。この各強連結成分を $1$ 頂点にまとめたグラフを縮約グラフと呼びます。この縮約グラフはDAGとなります。

最終的に生存している囚人の集合を $S$ としたとき、この集合が実現可能であるための必要十分条件は以下の通りです。

• 縮約グラフの入次数が $0$ の各強連結成分に、 $S$ に含まれる囚人が少なくとも $1$ 人存在する。

証明

必要性

入次数が $0$ の強連結成分を一つ考えます。

この成分の囚人を殺害できるのは、同じ成分に属する囚人だけです。成分内に生存者が $1$ 人だけになったあと、その最後の $1$ 人を殺害することはできません。

よって、この成分には少なくとも $1$ 人の生存者が必要です。

十分性

$S$ が上の条件を満たしているとします。

DAG の各頂点には、入次数が $0$ のいずれかの頂点から到達できます。また、同じ強連結成分に属する頂点どうしは互いに到達可能です。

したがって、すべての頂点に、 $S$ に含まれるいずれかの頂点から到達できます。

さらに、 $S$ に含まれない各頂点 $v$ について、 $S$ に含まれる頂点から $v$ への最短距離が遠い順に殺害していくことで、実際に達成することができます。

必要性と十分性が両方とも示せたので、これは必要十分条件です。□

強連結成分 $C$ の頂点数を $s$ とします。

• 縮約グラフでの入次数が $0$ の場合：少なくとも $1$ 人を生存させる必要があるため、生存者の選び方は $2^s-1$ 通りです。
• 縮約グラフでの入次数が $1$ 以上の場合：全員を殺害する場合も含めて自由に選べるため、生存者の選び方は $2^s$ 通りです。

これらの選択は独立であるため、すべての連結成分について上記を計算した総積が答えです。

計算量は、各テストケースについて $O(N+M)$ です。