ShareOJ Programming Contest vol.1 E - Solicitation of Murder
- サイト
- ShareOJ
- コンテスト
- ShareOJ Programming Contest vol.1
- 問題
- E - Solicitation of Murder(常設版)
頂点 辺の有向グラフが与えられます。辺 は「囚人 は囚人 に殺意を持っている」ことを表します。「生存している で辺 があるものを選び、 を殺す」という操作を好きな回数行ったあと、生存している囚人の集合としてありうるものの個数を で割った余りを求める問題です。
テストケースは 個あり、 の総和と の総和はそれぞれ 以下です。
生存者の集合の条件
Section titled “生存者の集合の条件”グラフを強連結成分分解します。外から入ってくる辺がない強連結成分(入次数 の成分)を、ここでは始点成分と呼びます。
生存者の集合 がありうるのは、すべての始点成分に の頂点が 1 つ以上あるときで、そのときに限ります。
必要性. 始点成分 の頂点を殺せるのは、 の頂点だけです。 の頂点が全員殺されたとすると、 の中で最後に殺された頂点を殺した頂点は の中にいて、そのあとに殺されています。これは最後であることに反します。よって、 には生存者が残ります。
十分性. どの頂点も、どこかの始点成分から到達できます。強連結成分の中では互いに到達できるので、すべての始点成分に の頂点があれば、すべての頂点が のどれかの頂点から到達できます。そこで、 からの距離 を考え、 にない頂点を が大きい順に殺します。 の頂点 には、 で辺 がある頂点 があります。 は の頂点か、 よりあとに殺す頂点なので、 を殺すときにはまだ生きています。したがって、 を殺せます。
条件は成分ごとに独立です。
- 始点成分 では、空でない部分集合ならどれでもよいので 通りです。
- それ以外の成分 では、制限がないので 通りです。
これらの積が答えです。
C++
#include "shogo-library/base/all"#include "shogo-library/graph/graph.hpp"#include "shogo-library/graph/graph_util.hpp"#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
void solve() { LL(N, M); Graph<> g(N); rep(M) { LL(a, b); a--, b--; g.add_directed_edge(a, b); } vl dp(N); auto tmp = strongly_connected_components(g); mint ans = 1; for (const auto &f : tmp) { ll x = 0; for (ll u : f) { x |= dp[u]; } ans *= mint(2).pow(f.size()) - !x; for (ll u : f) { for (ll v : g[u]) dp[v] = 1; } } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); LL(T); rep(T) solve();}strongly_connected_components は強連結成分をトポロジカル順に返します。dp[v] は「すでに処理した成分から に入る辺がある」ことを表すフラグです。成分 f を見る時点で、f に外から入る辺はすべて前の成分から来ているので、x が なら f は始点成分です。成分の中の辺で立つフラグは、x を求めたあとに立てています。
使用ライブラリ:cpp_include@397a51d