AtCoder Beginner Contest 204が開始されました。
AtCoder Beginner Contest 204は終了しました。
強連結成分分解してDAG(有向非巡回グラフ)に変換します。
DAG上での到達判定は頂点\(u\)から到達できるかという情報を\(N\)個保持しておけばDPで\(O(N(N+M))\)で求めることができました。
C++のstd::bitsetや.NETのSystem.Collections.BitArrayなどで到達できるかを保持すると高速化が望めます。
std::bitset
System.Collections.BitArray
投稿日時: 最終更新: