競プロ向けではありません。

\(O(N+M+Q)\) 時間のアルゴリズムです。 \(K \leq N\) がない場合は \(O(N+M+Q+K)\) 時間です。実用上、 union-find などを用いる解法と比べるとかなり遅いです。

まず、 \(S _ {U _ i} = S _ {V _ i}\) となる辺すべてによってグラフを縮約します。これにより、 \(S _ {U _ i} \neq S _ {V _ i}\) を問題の制約に追加することができます。

辺 \( \lbrace U _ i , V _ i \rbrace \) は \( \lbrace S _ {U _ i} , S _ {V _ i} \rbrace \) で、クエリ \( \lbrace A _ i , B _ i \rbrace \) は \( \lbrace S _ {A _ i} , S _ {B _ i} \rbrace \) で問題を分割します。基数ソートを用いると \(O((M+Q)+K)\) 時間で分割できます。分割された問題それぞれは静的グラフの連結性クエリになります。

各問題で \(O(N+M+Q)\) 時間をかけてよければ次のアルゴリズムが考えられます。

初期化： \(T _ i \leftarrow i\) \((1 \leq i \leq N)\)

1. 辺集合から隣接リストに追加
2. まだ見ていない頂点 \(s\) で、それを含む連結成分を幅優先探索で求める
3. 各連結成分 \(C\) で、 \(C\) に含まれる \(v\) について \(T _ v\) を代表元で塗る
4. \((u,v)\) の連結性を \(T _ u = T _ v\) かどうかで判定
5. \(T _ s \leftarrow s\)
6. 頂点 \(s\) の隣接リストをクリア

このアルゴリズムで \(s\) と表した頂点が「すべての頂点」でなく「辺の端点として現れるすべての頂点」としてもアルゴリズムは正しいです。あらかじめ確保された配列を繰り返し参照することで、分割後の各問題の計算量は \(O(m+q)\) ( \(m\) は辺の個数、 \(q\) はクエリの個数) 時間になります。

よって、全体で \(O(N+M+Q+K)\) 時間です。

解答例 (C++, 507 ms)