解説:#16 Dynamic connectivity
製作者:QCFium
## 解説
### 小課題1
$O(NQ)$かけてよいです。
グラフを隣接リスト(各頂点について、隣接する頂点を入れたvectorを持っておく方式)で管理し、連結かどうかの判定は幅優先探索(または深さ優先探索)をすればよいです。
実装例は以下の通りです。
```
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
int main() {
int n = ri(), q = ri();
assert(n <= 1000 && q <= 1000);
std::vector<std::vector<int> > hen(n); // 隣接リスト
for (int i = 0; i < q; i++) {
int t = ri();
int x = ri() - 1;
int y = ri() - 1;
if (t == 1) {
hen[x].push_back(y);
hen[y].push_back(x);
} else if (t == 2) {
hen[x].erase(std::find(hen[x].begin(), hen[x].end(), y));
hen[y].erase(std::find(hen[y].begin(), hen[y].end(), x));
} else if (t == 3) {
std::vector<bool> used(n);
std::queue<int> que;
que.push(x);
used[x] = true;
while (que.size()) {
int j = que.front();
que.pop();
for (auto k : hen[j]) {
if (!used[k]) {
used[k] = true;
que.push(k);
}
}
}
puts(used[y] ? "Yes" : "No");
}
}
return 0;
}
```
### 小課題2
辺の追加/連結性判定が高速にできればよいです。
これはUnionFindというデータ構造でできます。
互いにパスが存在するような過不足ない頂点集合のことを「連結成分」と呼びます。
UnionFindでは、各頂点が1つ以下の「親」を持ちます。最初の辺のない状態ではすべての頂点が「親」を持ちません。親を持たない頂点は各連結成分にちょうど1つ存在し、その連結成分の「根」と呼ぶことにします。(この「根」が連結成分内のどの頂点になるかは元のグラフの形状とはあまり関係しません。)親の親の...と親を持たない頂点までたどると、その連結成分の根にくるようにします。
- 連結かの判定
それぞれの頂点から親を辿って同じ頂点につけば同じ連結成分にいます。そうでなければ違う連結成分にいるのでそれらは連結ではありません。
- 辺の追加
まずもともと連結な2頂点であれば何もしません。
そうでない場合、2頂点の連結成分の根をそれぞれ$x,y$とおきます。$x$の親を$y$にすれば「親」や「根」の性質が保たれることがわかります。
これで正しい答えを出すことはできますが、親を辿るパスの長さは$N$に対して線形に長くなり得るので最悪計算量が1クエリあたり$\Theta(N)$となり、困ります。
ここで「各連結成分の根にその連結成分のサイズを持っておき、辺追加のときにサイズの小さいほうの親を大きいほうにする」という工夫を考えます。
すると各頂点について、連結成分の根が親を持つようになるのは自分が所属していた連結成分よりも小さくない連結成分と併合された場合に限るので、根との距離が1増えるごとに自分の所属してる連結成分のサイズは$2$倍以上になります。よって根との距離は$log_2{N}$を超えません。
ということは親を辿るコストが$O(logN)$なので1クエリ$O(logN)$で答えることができます。
実装例は以下の通りです。この実装ではdataという配列に「親があるなら親のindex, 親がないなら連結成分のサイズ$\times -1$」を入れてあります。
```
#include <bits/stdc++.h>
struct UnionFind {
std::vector<int> data;
UnionFind (int n) : data(n, -1) {}
// 親を辿って根を返す
int root(int i) {
if (data[i] < 0) return i;
else return root(data[i]);
}
// 連結性判定
bool is_connected(int x, int y) {
return root(x) == root(y);
}
// 辺の追加
void add_hen(int x, int y) {
x = root(x);
y = root(y);
if (x == y) return;
if (data[x] < data[y]) std::swap(x, y); // xの親をyにするのでxがより小さい連結成分になるようにする
data[y] += data[x];
data[x] = y;
}
};
int ri() {
int n;
scanf("%d", &n);
return n;
}
int main() {
int n = ri(), q = ri();
UnionFind uni(n);
for (int i = 0; i < q; i++) {
int t = ri();
int x = ri() - 1;
int y = ri() - 1;
if (t == 1) uni.add_hen(x, y);
else if (t == 2) assert(0);
else if (t == 3) puts(uni.is_connected(x, y) ? "Yes" : "No");
}
return 0;
}
```
### 満点
UnionFind自体はどう頑張っても高速に辺を削除することはできません。
そしてこの問題をオンライン(次のクエリを見る前に今のクエリを処理する方式)で解くのは非常に面倒です。そのためオフライン(クエリを先読みしてまとめて処理する方式)で解きます。
ここで$Q$個のクエリを時系列だと考えます。するとグラフは「$a$と$b$を結ぶ辺が時刻$l$から$r$まで存在した」という情報$O(Q)$個で表すことができます。
長さ$Q$のセグ木に似た完全二分木構造を構築し、上の各情報について$[l,r]$の区間に対応する$O(logQ)$個のノードに$(a,b)$を記録しておきます。
このセグ木上でdfs(深さ優先探索)をします。一番上のノードから開始し、左側の子,右側の子の順に潜ります。
UnionFindを1つだけ持ち、潜るときに潜る先のノードに記録されている辺を追加することを考えます。dfsが葉までこれば、その葉に対応するクエリの時点での連結性状態がUnionFindから得られます。問題は潜りから戻ってくるときです。この際最後に追加した辺の削除が必要です。
しかしUnionFindに要求されている操作は大幅に弱くなりました。辺の追加/最後の追加のキャンセル/連結性の判定ができればよいです。
UnionFindといえども中にある親を記録する配列を辺追加時に更新しているだけです。そして操作の中身を考えると辺の追加では定数個の書き換えしか行っていません。そのため書き換える際に位置と元の値を持っておくと書き換えのキャンセルができます。すると最後の辺の追加で行われた書き換えをキャンセルことで最後の辺追加をキャンセルしたことになります。
これで最後の追加のキャンセルは定数時間で処理ができることになりました。
ノードには合計で$O(QlogQ)$個の辺が記録されていて、全部1回ずつUnionFindに追加/キャンセルされるので全体で$O(Q\log Q\log N)$で処理できます。