Codeforces Round #561 F. Vicky's Delivery Service
お題箱より。
問題概要
頂点
辺の無向グラフがあり、各辺は
色のうちどれかの色で塗られている。
以下のクエリを 個処理せよ。
+ x y z頂点間に色
の辺を追加する。
? x y頂点から頂点
までの、以下の条件を満たすパスが存在するかどうか答える。
- 始点から1本目と2本目の辺の色が同じ、3本目と4本目の辺の色が同じ...というように、2本ずつ同じ色の辺を通る。（ただしパス長が奇数である場合、最後の辺には条件がない）
制約
- 全ての時点において、自己ループと多重辺は存在しないことが保証される
解法
メインの考え方
まず奇数長のパスは考えないことにしましょう。偶数長であり、ある頂点 から2本ずつ同じ色の辺を渡るパスを「良いパス」と呼ぶことにします。
ある頂点 から良いパスによって到達できる頂点たちを考えます。するとこれらの頂点たちの中からどの2頂点を選んでも、その間は良いパスで互いに到達できるはずです。これらの頂点を
として、
との良いパスを繋げた
というパスはやはり良いパスになっているからです。
そのため、この「良いパスによって互いに到達可能な頂点の集合」をUnion-Findで管理することができます。
まず最初の時点でのグラフについて、この集合はどのように求めることができるでしょうか？効率の良い方法は「長さ2の良いパスの、真ん中に注目する」ことです。ある頂点（図中の仲介役）から同じ色の辺が2本出ていれば、その相手同士は長さ2の良いパスで互いに到達可能ということになります。
このとき全てのペアを連結しようとする必要はなく、図のように併合をしていけば併合回数はおよそ辺の数の2倍で抑えることができます。
まずはこの処理を、全ての点を仲介役として回します。これで最初の時点での集合が作れます。
1クエリの処理
次にこのグラフに 1 x y z クエリで辺を追加する方法を考えます。その場合も先程と同じように、頂点 それぞれについて、その頂点を仲介役と見たときにどの頂点同士が良いパスで到達可能になるかを考えればよいです。
2クエリの処理
最後に 2 x y クエリ、ここで奇数長のパスを考え始めましょう。問題の条件を満たすパスは「良いパス」または「良いパスの最後に1回の移動をしたもの」になります。前者は同じ集合に入っているか調べればいいので簡単ですが、後者が厄介ですね。
併合した集合それぞれに対して、「含まれる頂点のどこかから移動1回で到達できる頂点の集合」を管理することにしましょう。説明のため「隣接点集合」という名前を付けておきます。
そうすると、「良いパスの最後に1回の移動をしたもの」によって始点から終点に移動できる条件は、始点が含まれる集合の隣接点集合に終点が入っていることです。この集合を管理できていれば答えがすぐに求められそうです。
隣接点集合の初期値としては単純に各頂点の隣接点を入れておけば良いです。頂点集合をマージしたときに、それらの隣接点集合もマージする必要があります。これはいわゆる「データ構造をマージする一般的なテク」により、要素数の小さいほうから大きい方にマージすることで計算量を抑えることができます。
1クエリで辺が増えたときには、こちらの隣接点集合にも追加する必要があることに気をつけてください。
これで全ての処理を扱う方法を揃えることができたので、問題を解くことができます。
ACコード
Submission #54314619 - Codeforces
説明と少し違う点として、隣接点集合に各頂点自身も含むようにしています。こうすると先程の「良いパス」と「良いパスの最後に1回の移動をしたもの」の両方を隣接点集合を見ることでチェックできるので少し楽です。
