任意のグラフ \(G\) と、\(G\) において長さ \(2\) のウォークが存在する頂点間に辺を張ったグラフ \(G'\) を考えます。

ここで、\(G\) のある頂点 \(w\) と、\(w\) に隣接する頂点の集合を \(N(w)\) を考えると、\(N(w)\) の任意の \(2\) 頂点 \(u,v\) の間には長さ \(2\) のウォークが存在します。すなわち、\(G'\) において頂点 \(u,v\) は連結です。このことから、\(G\) のある \(2\) 頂点 \(u,v\) の間に偶数長のウォークが存在するとき、\(G'\) において \(u,v\) は連結であることが言えます。

逆に、グラフ \(G'\) において \(2\) 頂点 \(u,v\) が連結であるとき、グラフ \(G\) において頂点 \(u,v\) の間に偶数長のウォークが存在することは簡単に示すことができます。

以上の議論より、以下の2つの命題は同値です。

• \(G\) において、頂点 \(u\) と頂点 \(v\) の間に偶数長のウォークが存在する。
• \(G'\) において、頂点 \(u\) と頂点 \(v\) が同じ連結成分に属する。

よって、\(G'\) の状態をシミュレーションすることで、クエリに高速に答えることができます。具体的には、各クエリに対して以下のような処理を行えばよいです。

• タイプ1のクエリ：
  • 頂点 \(u\) と頂点 \(v\) 隣接頂点の一つを併合する
  • 頂点 \(v\) と頂点 \(u\) 隣接頂点の一つを併合する
• タイプ2のクエリ：
  • 頂点 \(u,v\) が同一の集合に属する場合 Yes 、そうでない場合は No を出力する

このような操作は素集合データ構造によって、クエリあたり \(O(\alpha(N))\) 時間で実現できます。 ただし \(\alpha(N)\) は逆アッカーマン関数として知られる関数です。

クレジット

原案： NokonoKotlin

解法： NokonoKotlin

問題準備・解説： powell

レビュー： Jinapetto

テスター： tatyam

校正： nu50218