現在の進捗
満点解法まで作成済みです。
他の問題はこちらから。
https://qiita.com/clara775/items/57dbe85edcad1f4483c8
問題
日本語問題文はこちら
問題概要
N頂点M辺を持つ有向グラフと、K個の禁止された有向辺が与えられます。
根に辺がすべて向かい、与えられた有向グラフを完全に含み、さらに禁止された有向辺を含まないような木を構築しなさい。
この解説では、$(u,v)$を頂点$u$から頂点$v$へ向かう辺とします。また、使わなければいけない$M$辺を「良い辺」、禁止された$K$辺を「悪い辺」と呼ぶことにします。
小課題1 M=0, K=1
この小課題はad-hocで、満点解法につながるものではありません。次の二つの木を考えます。
- すべての辺が$(i,i+1)$であるような木
- すべての辺が$(i+1,i)$であるような木
このうちのどちらかは悪い辺を含まないので、そちらを出力すれば良いです。
小課題2 M=0, K=2
この小課題もad-hocで、満点解法につながるものではありません。
悪い辺の数が極端に少ないので、すべての頂点を使ったパスをランダムに考え、悪い辺を含まなければ出力するという方法で何回かの試行の後に正解を得ることができます。
ただし$N=2$の時はコーナーケースで、この場合条件を満たすグラフは存在しません。
もう一つの方法は、$N \geq 3$の時必ず悪い辺が向かわない頂点が存在することを使い、その点を根にするというものです。そして、他のすべての頂点を根へ直接繋げます。
小課題3 K=0
悪い辺が存在しないので、良い辺をすべて使った木を出力すれば良いことになります。
良い辺がもし有向の森を形成するなら、条件を満たすグラフが存在します。有向の森を形成しないとき、そのようなグラフは存在しません。有向の森が形成される具体的な条件は、
- 各頂点の出次数が高々1
- サイクルを含まない
サイクルを含むかどうかは、DFSでグラフを辿ることで確認できます。そのほかには、Union-Findで新たに辺$(u,v)$を繋ぐ時、頂点$u$と頂点$v$が既に同じ連結成分にいないか確認することでも確かめられます。
条件を満たすグラフが存在するなら、森の中の木を一つ選び、その根をグラフ全体の根として残りの木の根を繋げれば良いです。
小課題4 Nが100以下
小課題3の解法から考え始めます。まず、悪い辺が存在するようになっても、良い辺は有向の森を形成しなければならないのは変わりません。
これをチェックした後、形成された森について考えます（この時、いくつかの木は一つしか頂点を含まない可能性に注意してください）。最終的なグラフでは、森の中から一つ木を選んでそれを「根の木」として、他の木の根を「根の木」に繋げる必要があります。この時、他の木は根の木に直接つながっていないかもしれないことと、新しく構築する辺は木の根から他の木の任意の頂点へ向かうことに注意しておきましょう。
そこで、どの木が「根の木」になるかを全探索することを考えます。
ある「根の木」を固定して、「根の木」の根の頂点からDFSを行います。新たに頂点を訪れる時、そこからまだ繋げていない他の木の根に繋げるかどうかを確認し、悪い辺でなければ辺を構築することを繰り返します。これを繰り返してもし一つの木が作れなければ、「根の木」を変えて同じことを繰り返します。
この解法の計算量について考えます。「根の木」を固定した時、1回のDFSで辿る辺の数は高々$N-1$本です。また、根の木を決めてからDFSする処理が失敗するのは、悪い辺の数を考えると最大でも$K$回です。それぞれの辺が悪い辺か確かめるのに$O(\log N)$かかるので、「根の木」一つについての計算量は$O((N+K)\log N)$になります。
最後に、「根の木」になりうる木の数は最大で$N$個あるので、全体計算量は$O((N+K)N \log N)$になります。
別解では、悪くない辺が最大で$N^2-K$本あるので、それらの完全グラフを構築し、各頂点を根と決めてDFSを走らせて、木になるか確かめることもできます。この場合の計算量は$O(N^3)$になります。
小課題5 0が根であるような解が存在する
もうどれを根にすれば良いかわかっているので、計算量で$N$を一つ減らし$O((N+K)\log N)$にすることができます。この時、$N=300 000$でも十分間に合います。
しかし、完全グラフを構築してDFSする方法は根が0とわかっていても計算量$O(N^2)$になるので、小課題5では間に合いません。
小課題6 満点解法
小課題4を高速化することを考えましょう。
まず、どれを根として選ぶのが良いか、「良い根」であるかを考えます。簡単のため、$M=0$の時を考察してみましょう。この時、良い根とは悪くない辺で構成された完全グラフにおいて、すべての頂点から行ける頂点になります。
この考察のもと、辺をすべて逆向きにしてからDFSを頂点$v_0 := 0$から始めます。もしDFSの後すべての頂点を訪れていたら、0は良い根といえます。もし訪れていない頂点があれば、その一つ$v_1$からまたDFSを行います。この時、訪れたか否かのステータスはリセットしないでおきます。これを繰り返すと、いつかはすべての頂点を訪れることができます。
ここで最後にDFSを始めた点、$v_k$が良い根であるか考えてみましょう。$v_k$は孤立した点である可能性もあるので、常に良い根であるとは限りません。しかし、少なくとも$v_k$より前に訪れた頂点は良い根ではないことがわかります（もしそうであれば、$v_k$も訪れることができたはずだから）。また、$v_k$よりも後に訪れた頂点はすべて$v_k$から到達可能です。よって、$v_k$よりも後に訪れた頂点$i$が良い根であるなら、頂点$i$からすべての頂点に到達可能であり、よって頂点$v_k$からも頂点$i$を経由してすべての頂点に到達可能なので、$v_k$も良い根であるとわかります。
よって、$v_k$が良い根であるか、そうでないなら良い根は存在しないことになります。
$v_k$が良い根であるかどうかは、訪れたことがあるかのステータスをすべてリセットし、もう一度DFSをしてすべての頂点を訪れることができるかチェックすれば良いです。
このアルゴリズムは、強連結成分分解のアルゴリズム（Kosaraju's algorithm：DFSをし、帰りがけ順で逆向きのグラフをDFS）から思いつくことができます。
ここまで$M=0$の場合を考えてきましたが、これを簡単に$M > 0$の場合にも応用することができます。良い辺が有向な森を形成する時、それぞれの木を根の一頂点に圧縮することで、$M=0$の場合と同じように考えることができます。
小課題6は、満点解法を思いついたものの、良い辺の処理で何か実装が間違っている場合の保険として設定されています。