在读的文章

A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time

FULLY DYNAMIC STRONG CONNECTIVITY WITH PERSISTENCY

The algorithm handles each insert operation in worst-case time and each deletion operation in amortized time, and each query in time. The space complexity of the algorithm is

插入和删除都可以对任意边集操作；每次插入会新建一个版本的图，删除则会从所有当前存在的版本中把要删除的边集删掉。

’s SCC is either a SCC of or a union of some SCCs of ;

的所有SCC(不同G中相同SCC只记录一个)可以构成森林。叶子是单个的点。 The parent of a component w in the forest is the smallest component that strictly contains w.

下面提出一个edge partition 的概念用来维护上述森林。

Dynamic edge partitioning:

中的边是 中的SCC里面的边，并且要么在 中没有出现，要么在 中是不同SCC之间的边。

用两个数组parent和version来记录森林中每个节点的父亲和最早出现的版本（version记录最早那一次插入操作后出现了这个scc）。

现在要查询 中的两个点u,v是否在同一个SCC中，只需要在森林中查找u,v的LCA，如果version[LCA]小于等于i，说明u,v在同一个SCC中。（存在LCA说明在同一棵树，在某个版本u,v是在一个SCC中的，这个版本就是version[LCA]）

文中要使用tarjan的LCA算法均摊 的单次询问和 预处理（并查集使用路径压缩）。

Insert & Delete Operation

初始化： 是空图，森林是n个孤立的点，version都是0；

Insert:

进行第t个插入操作，插入的边集是 ：

首先根据 dynamic edge partitioning 的过程， 已经存在并且里面有 中SCC之间的边.

  2. a temporary set of edges is created by contracting the endpoints of edges with respect to the components of .
  3. compute SCC in
  4. for each SCC(denoted C) in , union vertices in C, update version and parent
  5. move edges which shouldn’t in to
  6. preprocess LCA
  7. t=t+1

解释一下第二步： 中的边是新加入的边和 中SCC之间的边，同一个scc中的点可以看成是一个点（因为在联通性方面他们等价），于是直接用其中一个点来代替他们。如果在 中形成了SCC，那么每个SCC中的点就会形成一个大的SCC，再把他们union起来。思想就是使用并查集来维护不断插入边来维护SCC的过程。

Delete:

delete操作十分暴力，直接破坏维护的整个并查集结构然后重新构建。

  1. for each , parent[ ]=null;
  2. do insert k times (k versions)

复杂度证明略。见论文。 （也提到了删除操作的 amortized time中的t是由于 要遍历t个 集合造成的，但是由于每次至少插入一条边，t一定小于m，所以也可以去掉）

Identify and Report Decompositions of SCC

观察到无论是insert还是delete任意边集E，每个SCC在森林中的version不会减少。（insert只能增加version；delete一些边，相同的SCC只能在相同时间或者更晚形成。）

如果一个SCC在delete操作时被分开了，我们希望找到他在新的森林中对应的最大的儿子是哪些。

part操作：对于一个SCC（记为C），找到他子树中节点在delete操作之后的森林中的对应（记为集合S）。可以保证这些点的并集一定是C，但是不能保证S中的SCC都是最大的。

统计S中所有节点的父亲（如果没有父亲就跳过）记为集合T（其实是一个按version排列的优先队列）.每次取T中version最小的节点u，如果u的儿子都属于S，就把u的儿子从S中删除，S中加入u，且把u的父亲也加入T。

然后有split操作对于给定的delete前的SCC v和version i，得到delete后分成了哪些version小于等于i的点：

DECREMENTAL MAINTENANCE OF REACHABILITY TREES

reachability tree是用来维护对于某个点r的联通性的数据结构。每个节点是一个SCC，根节点是包含r的一个SCC，如果图中的某个SCC不在树中，说明从r不能到达这个scc中的节点。

For every component w of the graph, the algorithm maintains a doubly linked list active[w] that contains all the active vertices of the component. A vertex v is active if it has uninspected inter-component incoming edges.

For every active vertex v, the algorithm maintains a doubly linked list in[v] containing all the uninspected inter-component edges that enter v.

For every vertex v, active or inactive, the algorithm maintains a doubly linked list out[v] containing all the edges emanating from v.

最开始所有边都是 uninspected，处理到一条边之后有两种情况： 1. 发现这条边没用，删掉 2. 这条边有用，变成 reachability tree 中的树边，保持 uninspected.

reachability tree 要保持这样的结构： >If w is a component of G, v >is the first vertex in active[w], and u is the first >vertex in in[v], then (u, v) is the tree edge connecting >component w to the tree. In particular, >if active[w] is empty, then w is not connected to >the tree and the vertices of w cannot be reached >from r.

为什么 in[v] 中只保存 inter-component 的边？

在SCC构成的森林中， intra-component 的边是自环，不可能成为树边，不要考虑他们。当 delete 操作之后，一个SCC中的 intra-component 边可能会变成 inter-component. 数据结构会维护这个部分。

当删除一些边的时候，要维护 reachability tree 就需要把删除边之后分裂的SCC找出、加入新的 inter-component 边，删除被删除的 inter-component 边。

但是这些操作可能会影响上面 reachability tree 要保持的结构，所以还需要再维护。

接下来只描述一下思想。

在 Identify and Report Decompositions of SCC 部分我们能得到任意一个SCC在 delete 操作之后会被 split 成新图中的哪些SCC。

可以得到一个被分裂出来的SCC的大小 和里面有哪些点 。

可以得到那些边从 intra-component 变成 inter-component.(比如被分开的SCC是 中的，那么这一步找到的改变状态的边就是 中被删除的边，根据 dynamic edge partitioning 中 的定义)

现在要维护出 中每个SCC的active链表。

中每个SCC的active链表中的点有两部分。一部分是由 的active链表中的点继承下来的，另一部分是因为 中的一些边被删掉了，某些点的入边从 intra-component 变成 inter-component ，导致这个点从 inactive 变为 active.

首先第二部分的点可以在更改边的状态时直接解决，这里不讨论。

第一部分的点有这样的做法。假设 中这些SCC的大小是递减的。首先构建 的active list，遍历 的active list中的点，把其中不属于a的都移动到其他某个 的active list中（注意分成的SCC是不可能有交集的）（这一步需要 。

下面文中说： >This makes a huge difference! If a vertex is moved from one active list to another, the size of the component containing it must have decreased by a factor of at least 2. Each vertex is therefore moved at most times and the total amount of time spent on constructing these lists is at most O(n log n).

不是很懂为什么size会减半，复杂度为什么是O(nlogn)

我的理解出现了问题，，，通过不断分解来把点塞到更小的SCC里面。每次需要O(n)的时间来判断原来SCC中一个active的点该放到哪个分裂出的SCC中，SCC最多需要logn次就会变成点，因此是at most O(n log n).

接下来 Reconnecting the tree after edge deletions

Let W be a set containing all the new components with no incoming tree edge, and all the old components that lost their incoming tree edges. (If the root r is contained in a new component, this new component is not added to W.) The set W can be easily constructed in O( | W | ) time.

删除一些边之后，原来的reachability tree可能会变成森林。森林中的树根显然就是W中的SCC（根据定义）（也有可能是r现在所在的SCC，r原来所在的SCC因为删边被破坏了）。

现在，我们想把W中的这些树根连起来，重新组合成r的 reachability tree

很容易想到利用上面早已构造好的 active 链表和 in 链表。

A vertex v whose list in[v] becomes empty ceases to be active and is removed from active[w].

如果在检查w的入边是否符合要求的时候发现并没有入边能符合要求，显然他是真的不行了，删边之后不会进入新的 reachability tree 了。但是还是要维护一下他的能到达的SCC（下面解释原因）。遍历他的出边（out[v]，v是w中的点)，如果out[v]中有边(v,u) 是 tentative tree edge，那需要把u所在的SCC加入W中。

这样做的原因：上面的标记 tentative tree edge 的步骤并没有考虑顺序，可能一些本来应该在新的 reachability tree 中的SCC直接连接到了某个已经不会在 reachability tree 里的SCC上面。为了防止漏掉SCC，要把不回进入新的 reachability tree 的SCC的 tentative tree edge 连接到的SCC重新加入W。

AN ALMOST LINEAR FULLY DYNAMIC REACHABILITY ALGORITHM

支持的操作：

  1. 插入：插入一些边（起始点或结束点都为同一个点）
  2. 删除：删除任意边集
  3. 询问：是否存在从u到v的路径

每次插入操作都会围绕一个中心点v，那就为v建立两棵 reachability tree，分别保存v能到达的点和能到达v的点（也相当于在原图和反图上建立上文的 reachability tree）这也是为什么上文 reachability tree 只需要处理删除操作。

查询是否存在从u到v的路径：检查是否存在这样一个w，使得u可以到达w（ ），而且w可以到达v（ ）. 这可以在 的时间内查找到。???

我思考了一下，不知道为何能在 回答询问。最坏情况要查找n个w，在reachability tree中并不能在常数时间内回答树中是否存在某个点。有点迷惑。insert操作的更新是重新构建一个 reachability tree ，如果两棵树上存在同一个节点，能不能保证他们的子树是相同的？如果能，图中所有不同的SCC的级别难道不是O(nlogn)吗？

发现理解错了active[w]，查询u是否在以w为根的 reachability tree 中只需要判断w树中的active[c[u]]是否为空即可。