ABC226E Just one

注:解説は独自のものなので、誤った部分がある可能性があります。

コンテスト中はしっかりと証明はできず、実際に書いてみて法則を探しました。証明ができていないと、考慮できていないケースなどが存在する場合が多々あるので、証明できるようにしたいところです。

入力例3にありますが、グラフは連結とは限りません。そこで、連結成分の内の一つについて考えます。

まず、入力例1から分かるように、閉路は条件を満たします。さらに、右回りと左回りの2通りが存在します。逆に、閉路内の頂点uは、閉路に属さない頂点vに対し、u->vと向きづけることはできません。なぜなら、頂点uが閉路外の頂点に向きづけられたとしたら、閉路内の頂点は順に頂点uに向かうように向きづけられ、最終的に閉路内の頂点の1つは他の頂点の2つに向きづけられてしまうからです。

また、この事実から閉路外の頂点は常に閉路に向かうように辺を向きづける必要があり、向きづけの方法は1通りです。

ここまでで、閉路がただ1つ存在するような場合は条件を満たすことがわかりました。

それでは、閉路が1つ以外の場合を考えます。

・閉路が0

すなわち、木の場合です。辺がただ1つしかない頂点はすべて自分から他方に向かうように辺を向きづける必要があります。そのまま、条件を満たすように向きづけを行うと、必ず1つの頂点で他方から自分に向きづけられた辺のみしかない頂点が存在することになります。(これは、その頂点を根としてBFSを行い、子から親に辺を向きづけていったものに一致します。)

よって、この場合0通りです。

・閉路が2個以上

閉路以外の頂点について、閉路に入るように向きづけを行うと必ず自分から他方に向かう辺を2つ以上もつ頂点が発生します。よって、この場合も0通りです。

以上から、すべての連結成分について閉路がただ1つであれば、連結成分の個数をとして、通りの向きづけの方法が存在することになります。

次に、閉路がただ1つか判定する方法を述べます。

判定方法：

ある連結成分について、Kruskal法で全域木を作る。この連結成分に属する辺のうち、全域木に使われなかった辺がただ1つなら閉路がただ1つ存在する。

この判定方法の正当性について、自分なりの証明を書いてみます。

前提として、木の性質に、「木に1つの辺を追加するとただ1つの閉路ができる」というものがあるので、これは成り立つものとします(R.J.ウィルソン著『グラフ理論入門』より)。

また、使われなかった辺が0なら閉路は0であるのは自明なので、使われなかった辺が少なくとも2つ存在すれば、閉路が2つ以上存在することを示したいと思います。

まず、全域木に使われていない辺の1つを追加すると、閉路が1つできます。これをCとします。

もう一つの使われていなかった辺をe=(u,v)とします。木であることから任意の頂点u,vには、パスPが存在します。

PとCが辺を共有しない場合、Cの2つの辺を切断して、u,vを含む部分グラフと含まない部分グラフに分離させます。すると、u,vを含むグラフは木となり、eを追加することで閉路が1つできます。切断した辺をもとに戻すと、Cとさらにもう一つの閉路Q={e,P}が存在することになり、閉路が2つ以上となることが示されました。

PとCが辺を共有する場合、こちらも辺の集合Q={e,P}は閉路となります。Cはeを含んでいないので、異なる閉路となり、閉路は2つ以上存在することが示されました。

自分の実装では、全域木の形成、連結成分へのindexの割り当て、使われなかった辺の分類と複雑化してしまいました。公式解説の通り、|V| = |E|となることを利用し、各連結成分ごとにDFSして、訪問した頂点数を合計して|V|に、各頂点の次数を合計して2で割って|E|を算出して判定する方がシンプルで良いと思います。

提出コード:https://atcoder.jp/contests/abc226/tasks/abc226_e

余談ですが、今回の問題と似たようなグラフ(各頂点の出次数が1の有向グラフ)は何回か出題されたように思います

そこで、定理として覚えておきたいと思います。

連結な有向グラフG=(V,E)について、

・全頂点の出次数が1

ならば、

・|V| = |E|

・閉路がただ1つ

・すべての頂点の有向辺を辿ると閉路に辿り着き、閉路内で循環する

必要性の証明

Gの部分グラフに、任意の頂点1つを追加し、uとおく。そこから、有向辺を辿って部分グラフに辺と頂点を追加していくと、必ず部分グラフに既に存在する頂点vに有向辺をもつ頂点rが出現する(そうでなければ、頂点が無限個あるか、出次数が0の頂点が存在することになる)。

頂点rを始点とする有向辺e=(r,v)は部分グラフに加えないでおく。そうするとu->v_1->...->rという部分グラフとなる。これは、rを根とする有向木の向きを全て逆向きにしたものと考えることができ、これを「rを根とする逆有向木」と定義する。

この状態の部分グラフに対して、部分グラフに含まれる頂点を終点にもつ有向辺(eを除く)とその辺の始点の頂点を部分グラフに加える。この操作を行った後の部分グラフも、rを根とする逆有向木となる。この操作をk回行った後にもrを根とする逆有向木であると仮定すると、k+1回目の操作を行って後もこれが成り立つ。

よって、追加できる頂点と辺が無くなるまでこの操作を繰り返してできる部分グラフはrを根とする逆有向木である。

追加する頂点が無くなった後、最後にeを部分グラフに追加する。すると、部分グラフに存在するvからrへのパス及びeによって、循環する閉路ができる。

vからrへのパスはただ一つなので、閉路もただ一つである。更にrを根とする有向木の逆向きなので、どの頂点から辿っても必ずrに行き着き、閉路に入りこむ。

また、各頂点を始点とする有向辺がただ一つ存在するので、頂点と辺は1対1対応でき、|V|=|E|となる。

これで必要性が示された。

十分性の証明

|V|=|E|であるため、出次数が2以上の頂点が存在すると仮定すると、出次数0の頂点が存在することになる。その頂点は行き止まりになってしまい、これは全ての頂点が閉路に向かうという仮定に反するので出次数は全て1である。

これで十分性が示された。