『アルゴリズムデザイン』3章演習問題

7種類

問題2

有名問題。

到達済み頂点を記録しながらBFSして、行きがけに閉路を検出したら、その閉路検出した頂点まで帰りがけに列挙する。

DAG列挙アルゴリズムで閉路が見つかったら改めて最初から閉路復元DFSするとか。

競プロ的にはACLのSCCを使うと簡単。

Union-Findで。

まず同種をUnionして、次に異種をFindして判定する。

やるだけ。頂点を1つ増やすと葉が1つ減って葉が2つ増えるので、頂点と葉の差は不変。

BFS木の任意の頂点vの隣接頂点は、「頂点vより深さが1小さい頂点が1個以下」「頂点vより深さが1大きい頂点が0個以上」である。ここでG≠Tと仮定してTに辺を足すと、「頂点vより深さが1小さい点が2個以上」あるいは「頂点vと同じ深さの頂点が1個以上」の頂点ができるが、その辺はDFS木で必ず通ることになるので、BFS木=DFS木に矛盾する。よって示された。

真。

全ての次数がn/2個の連結成分（つまり頂点がn/2+1個の完全グラフ）を1つ作ったら、残りの頂点数的がn/2-1個しかないので、もう1つ条件を満たす連結成分を作ることはできない。

真(c=3)

一直線のグラフが1番直径と平均距離が遠い。これは直径<平均距離にならないことから比率を大きくするには直径を伸ばすしかないことから帰納的に成り立つ。

一直線のグラフは頂点をN個として直径がN-1。平均距離は定義通りのΣ式を整理すると(N+1)/3。よって直径/平均距離の正の極限を取れば3。

sからtまでBFSしてsからの距離で番号を振る。tまでの距離をdとする。

1以上d未満のある距離の頂点が1つしかない場合、その頂点を破壊すればパスを破壊できる。逆に破壊されないためには1以上d未満の全ての距離に頂点が2つ以上含まれている必要があるが、その場合s, tを含めてグラフの頂点が2d以上になるので、「頂点をn個としてs, tの距離がn/2より大きい」に矛盾する。よって示された。

以上の手順にあるように（距離が1以上d未満で他に同じ距離がない）頂点vをO(m+n)で見つけることができる。

BFSしながらDPすればよい。

イベントソート。

感染クエリ、通信クエリ、判定クエリを時間でソートして順に操作すれば感染クエリと判定クエリが複数個ある問題でも解ける。

ウィルスが感染している頂点集合はHashSetで持ち、通信クエリで感染している頂点と通信した頂点を感染集合に加える。同じ時間の場合も適当に頑張ればいい。例えば「通信クエリの一頂点が感染頂点集合に含まれる場合、キューに入れる。そうでなければ別のHashSetに加えておく（この時、どちらの頂点からもHashSetを引けるようにしておく。例えばswapして2回入れればいい）」「キューから取り出して感染させる。感染先がHashSetにあれば取り出してキューに加える」みたいに。

DAGの到達可能性を判定する問題と解釈する。

クエリ１「PiはPjが生まれるよりも前に死んでいる」

クエリ２「PiとPjは生きていた期間が被る」

とする。

1. クエリ1について、PiからPjに有向辺を張る。

この時点で閉路があったら論外

2. トポロジカルソートする

このグラフで頂点vから頂点uに到達可能な時、「vはuが生まれるより前に死んでいる」と言える

3. 各クエリ2について「vからuに到達可能か」「uからvに到達可能か」を判定すればよい

頂点数をV、クエリ1の個数をE、クエリ2の個数をQとして、O((E+V)Q)になる。

3は基本的に毎回やるしかないはず（クエリ２が極端に多いなら全前計算すればいいが）