问题简介
\(\def\defopname#1{{\newcommand{#1}{{\operatorname{#1}}}}}\def\opname#1{{\defopname{#1}\mathbf{#1}}}\)动态地维护一张无向图 \(\newcommand{\G}{\mathcal G}\G\) ，支持加边 \(\opname{link}(v,w)\) 、删边 \(\opname{cut}(v,w)\) 两个操作，查询两个点之间的连通性 \(\opname{connected}(v,w) : \mathrm{Bool}\) 。在线。
要求复杂度在 \(O(\operatorname{polylog} n)\) 。
具体的描述与样例可以看 LOJ #122 。
算法描述
首先，如果这张图是树，那么动态树的维护是熟知的。
朴素的想法
我们只要取这张图上的（任何）一个生成森林 \(\newcommand{F}{\mathcal F}\F_0\) ，动态地维护它就可以简单地维护图上的答案。注意到我们需要额外数据结构维护非树边。
图上的 \(\link\) 只要判一下在不在同一个连通块里面，如果不在的话在 \(\F_0\) 上把他们 \(\link\) 起来。
图上的 \(\cut\) 如果删除的是非树边，直接从非树边集合中删除即可。如果删除的是树边，则树上的两侧可能需要被另一条（非树）边接起来。那么我们算法的核心就在于优化寻找重连边的复杂度。
更加朴素的想法
在我们找重连边时，一个 brute-force 的算法就是寻找一侧连通块所连出的所有出边，按某固定的顺序从前往后判断能不能重连。对这个算法的一个简单的 hack 是，假设知道切断 \((v_a,w_a)\) 之后，判断了 \((v_1,w_1),\cdots,(v_{k-1},w_{k-1})\) 不可用，然后重连了 \((v_k,w_k)\) 这条边，那么立刻切断 \((v_k,w_k)\) 之后朴素算法会需要重新遍历 \((v_1,w_1),\cdots,(v_{k-1},w_{k-1})\) 这些边，因此重复地立刻切断重连边可以把朴素算法搞炸。
由此我们自然想到，给每条边一个“不重要度”，每次一条边没有成功重连的时候把它的不重要度提升，以标记它们在某些情况下没有用。
优秀的想法
我们给每个边一个等级 \(\ell(e)\) 。我们需要保证它有一个上界 \(\ell_{\max}\) 。所有刚插入的边 \(\ell(e)=0\) 。我们维护 \(\ell\) 意义下的最大生成森林。
记 \(\G_i=\left(V=V(G),E=\left\{e\in E(\G)\mid\ell(e)\geq i\right\}\right)\) 是 \(\G\) 上所有等级 \(\geq i\) 的边构成的子图（并不需要显式地维护出来）， \(\F_i=\G_i\cap \F\) 是 \(\F\) 上等级 \(\geq i\) 的边构成的子森林。在我们的算法过程中不断维护如下性质：
- 性质 \((\alpha)\) ：\(\F_i\) 始终是 \(\G_i\) 的生成森林；也即， \(\F_i\) 的连通性与 \(\G_i\) 相同。注意到这条性质等于是说， \(\F\) 是 \(\G\) 上以 \(e\mapsto\ell(e)\) 为边权的最大生成树（证明：考虑 Kruskal 算法过程）。
- 性质 \((\gamma)\) ：\(\G_i\) 的每个连通块大小至多是 \(\left\lfloor 2^{-i}n\right\rfloor\) 。这可以用于保证边权上界是 \(\left\lceil\log_2 n\right\rceil\) 。
一条树边 \(e=(v,w)\) 被删除之后，我们需要寻找重连边 \(\mathrm{reconnect}\left(e,\ell\left(e\right)\right)\) 。
可以发现，由于性质 \((\alpha)\) 的存在，一条边 \(e\) 被删除之后的重连边 \(e'\) 一定满足 \(\ell(e')\leq\ell(e)\) ，否则就与 \(\F\) 的最大生成树性相冲突了。
为了保证最大生成树性质，我们按 \(\ell\) 的降序，从 \(\ell(e')=\ell(e)\) 开始寻找 \(e'\) ，然后不断递减。故我们定义如下寻找重连边的过程：
\(\opname{reconnect}(e=(v,w),k)\) ：在 \(\F_k\) 上，边 \(e\) 把原树分成两部分 \(\newcommand{\T}{\mathcal T}\T_v,\T_w\) 。不妨假设 \(\T_v\) 点数较小。我们把 \(\T_v\) 上所有等级恰好为 \(k\) 的边的等级提升到 \(k+1\) 。由于 \(\T_v\) 是较小的边，这没有破坏 \((\gamma)\) 。提升一条树边显然不会破坏 \((\alpha)\) 。
这之后，寻找所有 \(\T_v\) 连出的、等级为 \(k\) 的边尝试重连。如果可以重连则报告重连；结束。如果当前枚举到的边没有成功重连，那么这条边会被提升到 \(k+1\) 级。注意到此时这条边两侧都在 \(\T_v\) 里，而 \(\T_v\) 整个都在 \(\F_{k+1}\) 里，这没有破坏 \((\alpha)\) 。
如果在 \(k\) 这一层没有成功重连，那么再 \(\reconnect(e,k-1)\) 。
分析
上述过程中，我们可以发现：
- 每条边只被上移了 \(O(\log n)\) 次；这是因为 \(\forall e, \ell(e)\leq \log n\) 。
- 均摊来看，每条边只出现在 \(O(\log n)\) 次 \(\reconnect\) 里；这是因为 \(\reconnect\) 每次没有成功重连，都会把边上移，然后可以由 1. 推出。
- 同样由于等级上限限制，将一条边设为树边只需要做 \(O(\log n)\) 次树操作。
- 每次树操作都是可以用 ETT, LCT, Top Tree 之一完成，故“一次树操作”复杂度是 \(O(\log n)\) 。
综上，该算法的修改（均摊）复杂度是 \(O(\log^2 n)\) ，查询（等价于在 \(\F_0\) 上查询）的复杂度是 \(O(\log n)\) 。
实现的一些细节
由于 \(\reconnect\) 的需要，对于每个 \(x\) 、每个 \(l\) 我们需要维护从 \(x\) 出发、等级为 \(l\) 的非树边列表。另外，在动态树 \(\F_k\) 上我们需要枚举一个连通块（子树）中有哪些点有等级为 \(k\) 的非树边，故（ETT实现的话）我们可以对所有“有对应等级的节点”在动态树上打标记，在 ETT 的二叉树上维护二叉树的子树是否有被打标记的节点，然后递归下去寻找。可以证明这么做的复杂度是对的。注意到直接枚举子树的所有点、去寻找它们的出边的做法是错误的，这也是笔者第一次写 LibreOJ #122 的标算的时候所犯的错误之一。
另外，为了处理点和边之间的一大堆复杂的关系，可能需要若干个辅助
map
来记录点到边、点到层、层到边、边到点之间的对应关系，以及互相在某些列表里面的位置以便删除等等，在此不细讲。
代码
这里有一份 anta
写作的代码，取自于此处。代码风格很赞，就是比较长，可读性不太佳。里面有一些日语的注释，可以结合着谷歌翻译看一看。为了卡常，里面写了高贵的自底向上非旋转
Treap。其中的 HolmDeLichtenbergThorup::replace(int,int,int)
是算法核心。
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
struct Xor128 {
unsigned x, y, z, w;
Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
unsigned next() {
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
//手抜き
inline unsigned next(unsigned n) { return next() % n; }
};
//bottom upなTreap
//脱再帰！
//randomized binary searchにするにはchoiceRandomlyを
// bool choiceRandomly(Ref l, Ref r) { return rng.next(l->size + r->size) < l->size; }
//に書き換えるだけでよい。
template<typename Node>
struct BottomupTreap {
Xor128 rng;
typedef Node *Ref;
static int size(Ref t) { return !t ? 0 : t->size; }
unsigned nextRand() { return rng.next(); }
private:
bool choiceRandomly(Ref l, Ref r) {
return l->priority < r->priority;
}
public:
Ref join(Ref l, Ref r) {
if(!l) return r;
if(!r) return l;
Ref t = NULL;
unsigned long long dirs = 0;
int h;
for(h = 0; ; ++ h) {
if(h >= sizeof(dirs)*8 - 2) {
//dirsのオーバーフローを防ぐために再帰する。
//あくまでセーフティガードなのでバランスは多少崩れるかもしれない
t = join(l->right, r->left);
dirs = dirs << 2 | 1;
h ++;
break;
}
dirs <<= 1;
if(choiceRandomly(l, r)) {
Ref c = l->right;
if(!c) {
t = r;
r = r->parent;
break;
}
l = c;
}else {
dirs |= 1;
Ref c = r->left;
if(!c) {
t = l;
l = l->parent;
break;
}
r = c;
}
}
for(; h >= 0; -- h) {
if(!(dirs & 1)) {
Ref p = l->parent;
t = l->linkr(t);
l = p;
}else {
Ref p = r->parent;
t = r->linkl(t);
r = p;
}
dirs >>= 1;
}
return t;
}
typedef std::pair<Ref,Ref> RefPair;
//l＜t≦rの(l,r)に分割する
RefPair split2(Ref t) {
Ref p, l = t->left, r = t;
Node::cut(l); t->linkl(NULL);
while(p = t->parent) {
t->parent = NULL;
if(p->left == t)
r = p->linkl(r);
else
l = p->linkr(l);
t = p;
}
return RefPair(l, r);
}
//l＜t＜rの(l,t,r)に分割する。(l,r)を返す
RefPair split3(Ref t) {
Ref p, l = t->left, r = t->right;
Node::cut(l), Node::cut(r);
t->linklr(NULL, NULL);
while(p = t->parent) {
t->parent = NULL;
if(p->left == t)
r = p->linkl(r);
else
l = p->linkr(l);
t = p;
}
return RefPair(l, r);
}
Ref cons(Ref h, Ref t) {
assert(size(h) == 1);
if(!t) return h;
Ref u = NULL;
while(true) {
if(choiceRandomly(h, t)) {
Ref p = t->parent;
u = h->linkr(t);
t = p;
break;
}
Ref l = t->left;
if(!l) {
u = h;
break;
}
t = l;
}
while(t) {
u = t->linkl(u);
t = t->parent;
}
return u;
}
};
//free treeのために、辺を基本として扱う
class EulerTourTreeWithMarks {
struct Node {
typedef BottomupTreap<Node> BST;
Node *left, *right, *parent;
int size;
unsigned priority;
char marks, markUnions; //0ビット目がedgeMark, 1ビット目がvertexMark
Node(): left(NULL), right(NULL), parent(NULL),
size(1), priority(0), marks(0), markUnions(0) { }
inline Node *update() {
int size_t = 1, markUnions_t = marks;
if(left) {
size_t += left->size;
markUnions_t |= left->markUnions;
}
if(right) {
size_t += right->size;
markUnions_t |= right->markUnions;
}
size = size_t, markUnions = markUnions_t;
return this;
}
inline Node *linkl(Node *c) {
if(left = c) c->parent = this;
return update();
}
inline Node *linkr(Node *c) {
if(right = c) c->parent = this;
return update();
}
inline Node *linklr(Node *l, Node *r) {
if(left = l) l->parent = this;
if(right = r) r->parent = this;
return update();
}
static Node *cut(Node *t) {
if(t) t->parent = NULL;
return t;
}
static const Node *findRoot(const Node *t) {
while(t->parent) t = t->parent;
return t;
}
static std::pair<Node*,int> getPosition(Node *t) {
int k = BST::size(t->left);
Node *p;
while(p = t->parent) {
if(p->right == t)
k += BST::size(p->left) + 1;
t = p;
}
return std::make_pair(t, k);
}
static const Node *findHead(const Node *t) {
while(t->left) t = t->left;
return t;
}
static void updatePath(Node *t) {
while(t) {
t->update();
t = t->parent;
}
}
};
typedef Node::BST BST;
BST bst;
std::vector<Node> nodes;
//各頂点に対してその頂点から出ているarcを1つだけ代表として持つ(無い場合は-1)
//逆にarcに対して対応する頂点はたかだか1つである
std::vector<int> firstArc;
//辺・頂点に対する属性
std::vector<bool> edgeMark, vertexMark;
inline int getArcIndex(const Node *a) const { return a - &nodes[0]; }
inline int arc1(int ei) const { return ei; }
inline int arc2(int ei) const { return ei + (numVertices() - 1); }
public:
inline int numVertices() const { return firstArc.size(); }
inline int numEdges() const { return numVertices() - 1; }
inline bool getEdgeMark(int a) const {
return a < numEdges() ? edgeMark[a] : false;
}
inline bool getVertexMark(int v) const {
return vertexMark[v];
}
private:
void updateMarks(int a, int v) {
Node *t = &nodes[a];
t->marks = getEdgeMark(a) << 0 | getVertexMark(v) << 1;
Node::updatePath(t);
}
//firstArcの変更に応じて更新する
void firstArcChanged(int v, int a, int b) {
if(a != -1) updateMarks(a, v);
if(b != -1) updateMarks(b, v);
}
public:
class TreeRef {
friend class EulerTourTreeWithMarks;
const Node *ref;
public:
TreeRef() { }
TreeRef(const Node *ref_): ref(ref_) { }
bool operator==(const TreeRef &that) const { return ref == that.ref; }
bool operator!=(const TreeRef &that) const { return ref != that.ref; }
bool isIsolatedVertex() const { return ref == NULL; }
};
void init(int N) {
int M = N - 1;
firstArc.assign(N, -1);
nodes.assign(M * 2, Node());
for(int i = 0; i < M * 2; i ++)
nodes[i].priority = bst.nextRand();
edgeMark.assign(M, false);
vertexMark.assign(N, false);
}
TreeRef getTreeRef(int v) const {
int a = firstArc[v];
return TreeRef(a == -1 ? NULL : Node::findRoot(&nodes[a]));
}
bool isConnected(int v, int w) const {
if(v == w) return true;
int a = firstArc[v], b = firstArc[w];
if(a == -1 || b == -1) return false;
return Node::findRoot(&nodes[a]) == Node::findRoot(&nodes[b]);
}
static int getSize(TreeRef t) {
if(t.isIsolatedVertex()) return 1;
else return t.ref->size / 2 + 1;
}
void link(int ti, int v, int w) {
int a1 = arc1(ti), a2 = arc2(ti);
//v→wがa1に対応するようにする
if(v > w) std::swap(a1, a2);
int va = firstArc[v], wa = firstArc[w];
Node *l, *m, *r;
if(va != -1) {
//evert。順番を入れ替えるだけ
std::pair<Node*,Node*> p = bst.split2(&nodes[va]);
m = bst.join(p.second, p.first);
}else {
//vが孤立点の場合
m = NULL;
firstArc[v] = a1;
firstArcChanged(v, -1, a1);
}
if(wa != -1) {
std::pair<Node*,Node*> p = bst.split2(&nodes[wa]);
l = p.first, r = p.second;
}else {
//wが孤立点の場合
l = r = NULL;
firstArc[w] = a2;
firstArcChanged(w, -1, a2);
}
//w→vの辺をmの先頭＝lの末尾にinsert
m = bst.cons(&nodes[a2], m);
//v→wの辺をmの末尾＝rの先頭にinsert
r = bst.cons(&nodes[a1], r);
bst.join(bst.join(l, m), r);
}
void cut(int ti, int v, int w) {
//v→wがa1に対応するようにする
if(v > w) std::swap(v, w);
int a1 = arc1(ti), a2 = arc2(ti);
std::pair<Node*,Node*> p = bst.split3(&nodes[a1]);
int prsize = BST::size(p.second);
std::pair<Node*,Node*> q = bst.split3(&nodes[a2]);
Node *l, *m, *r;
//a1,a2の順番を判定する。a1＜a2ならp.secondが変わっているはず
if(p.second == &nodes[a2] || BST::size(p.second) != prsize) {
l = p.first, m = q.first, r = q.second;
}else {
//a2＜a1の順番である。v→wの辺がa1であって親→子であることにする
std::swap(v, w);
std::swap(a1, a2);
l = q.first, m = q.second, r = p.second;
}
//firstArcを必要に応じて書き換える
if(firstArc[v] == a1) {
int b;
if(r != NULL) {
//vが根じゃないなら右側の最初の辺でよい
b = getArcIndex(Node::findHead(r));
}else {
//vが根なら最初の辺でよい。孤立点になるなら-1
b = !l ? -1 : getArcIndex(Node::findHead(l));
}
firstArc[v] = b;
firstArcChanged(v, a1, b);
}
if(firstArc[w] == a2) {
//wが根になるので最初の辺でよい。孤立点になるなら-1
int b = !m ? -1 : getArcIndex(Node::findHead(m));
firstArc[w] = b;
firstArcChanged(w, a2, b);
}
bst.join(l, r);
}
void changeEdgeMark(int ti, bool b) {
assert(ti < numEdges());
edgeMark[ti] = b;
Node *t = &nodes[ti];
t->marks = (b << 0) | (t->marks & (1 << 1));
Node::updatePath(t);
}
void changeVertexMark(int v, bool b) {
vertexMark[v] = b;
int a = firstArc[v];
if(a != -1) {
Node *t = &nodes[a];
t->marks = (t->marks & (1 << 0)) | (b << 1);
Node::updatePath(t);
}
}
template<typename Callback>
bool enumMarkedEdges(TreeRef tree, Callback callback) const {
return enumMarks<0,Callback>(tree, callback);
}
//孤立点の場合は呼び側でその頂点だけ処理する必要がある
template<typename Callback>
bool enumMarkedVertices(TreeRef tree, Callback callback) const {
return enumMarks<1,Callback>(tree, callback);
}
private:
//callback : TreeEdgeIndex×2 -> Bool
//引数は頂点をそこからのincident arcで示し、"(正方向 ? 0 : N-1) + treeEdgeIndex"を表す。方向はv,wの大小で処理すればよい
//callbackは継続するかどうかをboolで返す。最後まで列挙し終えたかどうかを返す。
template<int Mark, typename Callback>
bool enumMarks(TreeRef tree, Callback callback) const {
if(tree.isIsolatedVertex()) return true;
const Node *t = tree.ref;
if(t->markUnions >> Mark & 1)
return enumMarksRec<Mark,Callback>(t, callback);
else
return true;
}
//平衡木なので深さは深くないので再帰して問題ない
template<int Mark, typename Callback>
bool enumMarksRec(const Node *t, Callback callback) const {
const Node *l = t->left, *r = t->right;
if(l && (l->markUnions >> Mark & 1))
if(!enumMarksRec<Mark,Callback>(l, callback)) return false;
if(t->marks >> Mark & 1)
if(!callback(getArcIndex(t))) return false;
if(r && (r->markUnions >> Mark & 1))
if(!enumMarksRec<Mark,Callback>(r, callback)) return false;
return true;
}
public:
//デバッグ用
void debugEnumEdges(std::vector<int> &out_v) const {
int M = numEdges();
for(int ti = 0; ti < M; ti ++) {
const Node *t = &nodes[ti];
if(t->left || t->right || t->parent)
out_v.push_back(ti);
}
}
};
//treeEdgeにはそれぞれ0～N-1のインデックスが与えられる。これは全てのレベルで共通。
//ところで"level up"って和製英語なんだ。promoteでいいかな。
//Sampling heuristic ランダムケースで超速く(4倍とか)なったんだけど！いいね！
//
//References
//・Holm, Jacob, Kristian De Lichtenberg, and Mikkel Thorup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM (JACM) 48.4 (2001): 723-760.
//・Iyer, Raj, et al. "An experimental study of polylogarithmic, fully dynamic, connectivity algorithms." Journal of Experimental Algorithmics (JEA) 6 (2001): 4.
class HolmDeLichtenbergThorup {
typedef HolmDeLichtenbergThorup This;
typedef EulerTourTreeWithMarks Forest;
typedef Forest::TreeRef TreeRef;
int numVertices_m;
int numSamplings;
//DynamicTreeはコピーできないけどまあその状態で使わなきゃいいじゃんということで…
std::vector<Forest> forests;
std::vector<char> edgeLevel;
std::vector<int> treeEdgeIndex; // : EdgeIndex -> TreeEdgeIndex
std::vector<int> treeEdgeMap; // : TreeEdgeIndex -> EdgeIndex
std::vector<int> treeEdgeIndexFreeList; // : [TreeEdgeIndex]
//arcも方向はEulerTourTreeと同じようにv,wの大小に合わせる
std::vector<int> arcHead;
std::vector<std::vector<int> > firstIncidentArc;
std::vector<int> nextIncidentArc, prevIncidentArc;
//一時的に使う。使い回して使う
std::vector<bool> edgeVisited;
std::vector<int> visitedEdges; // : [EdgeIndex | TreeEdgeIndex]
int arc1(int ei) const { return ei; }
int arc2(int ei) const { return numMaxEdges() + ei; }
int arcEdge(int i) const { return i >= numMaxEdges() ? i - numMaxEdges() : i; }
bool replace(int lv, int v, int w) {
Forest &forest = forests[lv];
TreeRef vRoot = forest.getTreeRef(v), wRoot = forest.getTreeRef(w);
assert(vRoot.isIsolatedVertex() || wRoot.isIsolatedVertex() || vRoot != wRoot);
int vSize = forest.getSize(vRoot), wSize = forest.getSize(wRoot);
int u; TreeRef uRoot; int uSize;
if(vSize <= wSize)
u = v, uRoot = vRoot, uSize = vSize;
else
u = w, uRoot = wRoot, uSize = wSize;
//replacement edgeを探す
int replacementEdge = -1;
enumIncidentArcs(forest, uRoot, u, lv, FindReplacementEdge(uRoot, &replacementEdge));
//"Sampling heuristic"
//早い時点で見つかったならT_u,他のincident arcsをレベルアップさせなくても計算量的に問題ない
if(replacementEdge != -1 && (int)visitedEdges.size() + 1 <= numSamplings) {
//replacementEdgeを処理する
deleteNontreeEdge(replacementEdge);
addTreeEdge(replacementEdge);
for(int i = 0; i < (int)visitedEdges.size(); i ++)
edgeVisited[visitedEdges[i]] = false;
visitedEdges.clear();
return true;
}
//見つけたincident arcsを一斉にレベルアップさせる。edgeVisitedの後処理もする
for(int i = 0; i < (int)visitedEdges.size(); i ++) {
int ei = visitedEdges[i];
edgeVisited[ei] = false;
deleteNontreeEdge(ei);
++ edgeLevel[ei];
insertNontreeEdge(ei);
}
visitedEdges.clear();
//このレベルのT_uの辺を列挙する
forest.enumMarkedEdges(uRoot, EnumLevelTreeEdges(this));
//列挙したT_uの辺を一斉にレベルアップさせる
for(int i = 0; i < (int)visitedEdges.size(); i ++) {
int ti = visitedEdges[i];
int ei = treeEdgeMap[ti];
int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
int lv = edgeLevel[ei];
edgeLevel[ei] = lv + 1;
forests[lv].changeEdgeMark(ti, false);
forests[lv+1].changeEdgeMark(ti, true);
forests[lv+1].link(ti, v, w);
}
visitedEdges.clear();
if(replacementEdge != -1) {
//T_uの辺列挙の前に構造が変わると困るのでreplacementEdgeはこのタイミングで処理する
deleteNontreeEdge(replacementEdge);
addTreeEdge(replacementEdge);
return true;
}else if(lv > 0) {
return replace(lv-1, v, w);
}else {
return false;
}
}
struct EnumLevelTreeEdges {
This *thisp;
EnumLevelTreeEdges(This *thisp_): thisp(thisp_) { }
inline bool operator()(int a) {
thisp->enumLevelTreeEdges(a);
return true;
}
};
void enumLevelTreeEdges(int ti) {
visitedEdges.push_back(ti);
}
//孤立点の時特別な処理をするなどしなければいけないのでヘルパー
template<typename Callback>
bool enumIncidentArcs(Forest &forest, TreeRef t, int u, int lv, Callback callback) {
if(t.isIsolatedVertex())
return enumIncidentArcsWithVertex<Callback>(lv, u, callback);
else
return forest.enumMarkedVertices(t, EnumIncidentArcs<Callback>(this, lv, callback));
}
template<typename Callback>
struct EnumIncidentArcs {
This *thisp;
int lv;
Callback callback;
EnumIncidentArcs(This *thisp_, int lv_, Callback callback_):
thisp(thisp_), lv(lv_), callback(callback_) { }
inline bool operator()(int tii) const {
return thisp->enumIncidentArcsWithTreeArc(tii, lv, callback);
}
};
template<typename Callback>
bool enumIncidentArcsWithTreeArc(int tii, int lv, Callback callback) {
bool dir = tii >= numVertices() - 1;
int ti = dir ? tii - (numVertices() - 1) : tii;
int ei = treeEdgeMap[ti];
int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
//方向を求め、そのarcのtailの頂点を取得する
int u = !(dir != (v > w)) ? v : w;
return enumIncidentArcsWithVertex(lv, u, callback);
}
//1つの頂点を処理する
template<typename Callback>
bool enumIncidentArcsWithVertex(int lv, int u, Callback callback) {
int it = firstIncidentArc[lv][u];
while(it != -1) {
if(!callback(this, it))
return false;
it = nextIncidentArc[it];
}
return true;
}
struct FindReplacementEdge {
TreeRef uRoot;
int *replacementEdge;
FindReplacementEdge(TreeRef uRoot_, int *replacementEdge_):
uRoot(uRoot_), replacementEdge(replacementEdge_) { }
inline bool operator()(This *thisp, int a) const {
return thisp->findReplacementEdge(a, uRoot, replacementEdge);
}
};
//1つのarcを処理する
bool findReplacementEdge(int a, TreeRef uRoot, int *replacementEdge) {
int ei = arcEdge(a);
if(edgeVisited[ei]) return true;
int lv = edgeLevel[ei];
TreeRef hRoot = forests[lv].getTreeRef(arcHead[a]);
if(hRoot.isIsolatedVertex() || hRoot != uRoot) {
//別の木に渡されているならreplacement edgeである。
*replacementEdge = ei;
return false;
}
//replacement edgeはvisitedEdgesに入れたくないのでこの位置でマークする
edgeVisited[ei] = true;
visitedEdges.push_back(ei);
return true;
}
void addTreeEdge(int ei) {
int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
int lv = edgeLevel[ei];
int ti = treeEdgeIndexFreeList.back();
treeEdgeIndexFreeList.pop_back();
treeEdgeIndex[ei] = ti;
treeEdgeMap[ti] = ei;
forests[lv].changeEdgeMark(ti, true);
for(int i = 0; i <= lv; i ++)
forests[i].link(ti, v, w);
}
void insertIncidentArc(int a, int v) {
int ei = arcEdge(a);
int lv = edgeLevel[ei];
assert(treeEdgeIndex[ei] == -1);
int next = firstIncidentArc[lv][v];
firstIncidentArc[lv][v] = a;
nextIncidentArc[a] = next;
prevIncidentArc[a] = -1;
if(next != -1) prevIncidentArc[next] = a;
if(next == -1)
forests[lv].changeVertexMark(v, true);
}
void deleteIncidentArc(int a, int v) {
int ei = arcEdge(a);
int lv = edgeLevel[ei];
assert(treeEdgeIndex[ei] == -1);
int next = nextIncidentArc[a], prev = prevIncidentArc[a];
nextIncidentArc[a] = prevIncidentArc[a] = -2;
if(next != -1) prevIncidentArc[next] = prev;
if(prev != -1) nextIncidentArc[prev] = next;
else firstIncidentArc[lv][v] = next;
if(next == -1 && prev == -1)
forests[lv].changeVertexMark(v, false);
}
void insertNontreeEdge(int ei) {
int a1 = arc1(ei), a2 = arc2(ei);
insertIncidentArc(a1, arcHead[a2]);
insertIncidentArc(a2, arcHead[a1]);
}
void deleteNontreeEdge(int ei) {
int a1 = arc1(ei), a2 = arc2(ei);
deleteIncidentArc(a1, arcHead[a2]);
deleteIncidentArc(a2, arcHead[a1]);
}
public:
HolmDeLichtenbergThorup(): numVertices_m(0), numSamplings(0) { }
int numVertices() const { return numVertices_m; }
int numMaxEdges() const { return edgeLevel.size(); }
void init(int N, int M) {
numVertices_m = N;
int levels = 1;
while(1 << levels <= N / 2) levels ++;
//サンプリング数を設定する。適切な値はよくわからない
numSamplings = (int)(levels * 1);
forests.resize(levels);
for(int lv = 0; lv < levels; lv ++)
forests[lv].init(N);
edgeLevel.assign(M, -1);
treeEdgeIndex.assign(M, -1);
treeEdgeMap.assign(N - 1, -1);
treeEdgeIndexFreeList.resize(N-1);
for(int ti = 0; ti < N-1; ti ++)
treeEdgeIndexFreeList[ti] = ti;
arcHead.assign(M * 2, -1);
firstIncidentArc.resize(levels);
for(int lv = 0; lv < levels; lv ++)
firstIncidentArc[lv].assign(N, -1);
nextIncidentArc.assign(M * 2, -2);
prevIncidentArc.assign(M * 2, -2);
edgeVisited.assign(M, false);
}
bool insertEdge(int ei, int v, int w) {
assert(0 <= ei && ei < numMaxEdges() && 0 <= v && v < numVertices() && 0 <= w && w < numVertices());
assert(edgeLevel[ei] == -1);
int a1 = arc1(ei), a2 = arc2(ei);
arcHead[a1] = w, arcHead[a2] = v;
bool treeEdge = !forests[0].isConnected(v, w);
edgeLevel[ei] = 0;
if(treeEdge) {
addTreeEdge(ei);
}else {
treeEdgeIndex[ei] = -1;
//ループは見たくないのでリストにも入れない
if(v != w)
insertNontreeEdge(ei);
}
return treeEdge;
}
bool deleteEdge(int ei) {
assert(0 <= ei && ei < numMaxEdges() && edgeLevel[ei] != -1);
int a1 = arc1(ei), a2 = arc2(ei);
int v = arcHead[a2], w = arcHead[a1];
int lv = edgeLevel[ei];
int ti = treeEdgeIndex[ei];
bool splitted = false;
if(ti != -1) {
treeEdgeMap[ti] = -1;
treeEdgeIndex[ei] = -1;
treeEdgeIndexFreeList.push_back(ti);
for(int i = 0; i <= lv; i ++)
forests[i].cut(ti, v, w);
forests[lv].changeEdgeMark(ti, false);
splitted = !replace(lv, v, w);
}else {
//ループはリストに入ってない
if(v != w)
deleteNontreeEdge(ei);
}
arcHead[a1] = arcHead[a2] = -1;
edgeLevel[ei] = -1;
return splitted;
}
bool isConnected(int v, int w) const {
return forests[0].isConnected(v, w);
}
};
int main() {
int N, M;
scanf("%d%d", &N, &M);
if((ll)N * (N-1) / 2 - M > N - 1) {
rep(i, M) {
int S, T;
scanf("%d%d", &S, &T);
puts("no");
}
return 0;
}
vector<vector<int> > edgeIndex(N);
int totalEdges = 0;
rep(i, N) {
edgeIndex[i].resize(i);
rep(j, i) edgeIndex[i][j] = totalEdges ++;
}
typedef HolmDeLichtenbergThorup FullyDynamicConnectivity;
FullyDynamicConnectivity fdc;
fdc.init(N, totalEdges);
vector<bool> edgeExist(totalEdges);
int numComponents = N, numEdges = 0;
//最初に完全グラフにする
rep(i, N) rep(j, i) {
int ei = edgeIndex[i][j];
numComponents -= fdc.insertEdge(ei, i, j);
edgeExist[ei] = true;
++ numEdges;
}
rep(i, M) {
int S, T;
scanf("%d%d", &S, &T), S --, T --;
if(S < T) swap(S, T);
int ei = edgeIndex[S][T];
if(!edgeExist[ei]) {
numComponents -= fdc.insertEdge(ei, S, T);
edgeExist[ei] = true;
++ numEdges;
}else {
numComponents += fdc.deleteEdge(ei);
edgeExist[ei] = false;
-- numEdges;
}
bool isForest = numEdges == N - numComponents;
puts(isForest ? "yes" : "no");
}
return 0;
}写在后面，一些垃圾话
三年了。果然 EtaoinWu 还是没有什么长进，写的东西还是三年前的老本呢（笑）
顿感高一的自己是多么能肝，而现在的自己已然颓废。在 osu! 上被推荐到《平凡之路》，五分钟的 beatmap 听到一半渐渐失去理智，遂下楼冷静了一下。感觉自己需要肝一点东西出来证明自己，遂有了这篇。
Reference
- Renato F. Werneck, Design and Analysis of Data Structures for Dynamic Trees.
- J. Holm, K. de Lichtenberg, and M. Thorup, Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.
- CS166 slides, Standford University.