动态图连通性的 Holm-de Lichtenberg-Thorup 算法

问题简介

\(\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)\)

分析

上述过程中,我们可以发现:

  1. 每条边只被上移了 \(O(\log n)\) 次;这是因为 \(\forall e, \ell(e)\leq \log n\)
  2. 均摊来看,每条边只出现在 \(O(\log n)\)\(\reconnect\) 里;这是因为 \(\reconnect\) 每次没有成功重连,都会把边上移,然后可以由 1. 推出。
  3. 同样由于等级上限限制,将一条边设为树边只需要做 \(O(\log n)\) 次树操作。
  4. 每次树操作都是可以用 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 来记录点到边、点到层、层到边、边到点之间的对应关系,以及互相在某些列表里面的位置以便删除等等,在此不细讲。

代码

优秀的参考代码可见,作者为 negiizhao

这里有一份 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

  1. Renato F. Werneck, Design and Analysis of Data Structures for Dynamic Trees.
  2. J. Holm, K. de Lichtenberg, and M. Thorup, Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.
  3. CS166 slides, Standford University.