洛谷P5247 动态图完全连通性 LCT解法

阅读量: searchstar 2021-11-20 23:03:34
Categories： Tags：

jerry3128 和 zghtyarecrenj 大佬都讲得很好，但是漏了一些细节。这里简单补充一点。

Holm-de Lichtenberg-Thorup 算法的原始论文：https://u.cs.biu.ac.il/~rodittl/p723-holm.pdf

算法的简化描述如下。

给边分层，每条边一开始都在第 0 层，然后之后可以移到上层，定义 l(e) 为边 e 的层号。定义 Gi 为所有层号小于等于 i 的边构成的图。令F0 为 G0 的生成树森林，令 Fi 为 Gi ∩ F0。令 Ti为 Fi 中层号刚好为 i 的边的集合，即层号刚好为 i 的树边的集合。令 Ni 为 Gi − Fi 中层号刚好为 i 的边的集合，即层号为 i 的非树边的集合。下面我们只维护 Fi、Ti、Ni。

我们维护这几个性质：

  1. 对任何非树边 e = (x,y)，x 和 y 都在 Fl(e)中连通。

  2. Fi 中每个连通分量的节点数最多为 ⌊n/2i⌋，这样最大的层号 lmax就是 ⌊log2(n)⌋。

  3. 对任何树边 e = (x,y)，对任何 i > l(e)，x 和 y 在 Fi中都不连通。

直接查询 x 和 y 在 F0 中是否连通即可。

令 l(e) = 0，然后判断 x 和 y 是不是连通的，如果连通说明它是非树边，将其加入到 N0 中。如果不连通说明它是树边，加入到 F0 和 T0 中。

先看 x 和 y 在不在 Nl(e) 中，如果在就可以直接从 Nl(e) 中删掉它，不影响连通性。

如果不在 Nl(e) 中，那肯定在 Tl(e)中。将其从 Tl(e)，以及 F0, F1, ⋯, Fl(e) 中删去。然后我们就要尝试找一条边将 x 和 y 所在的连通分量重新连接起来，由于性质 1 和性质 3，这样的边的层号必须小于等于 l(e)。我们从 l(e) 层开始，一直尝试到第 0 层，如果在某层找到了，就成功，否则就失败。

假设 X 为 x 所处的连通分量，Y 为 y 所处的连通分量。不失一般性，假设 X 的节点数不多于 Y 的节点数。我们搜索所有在 X 中的非树边 e = (u,v)，如果 v 在 Y 中的话，就说明 e 可以连接两个连通分量，将 e 从非树边变成树边，即将 e 从 Nl 中删除，并把 e 加入到 Tl 以及 F0, F1, ⋯, Fl 中。

如果 v 不在 Y 中，那肯定在 X 中。我们将 e 移动到上层去，即令 l(e) 自增 1。因为我们要维护性质 1，所以我们要保证 u 和 v 在 Fl + 1 中连通。我们发现，只要我们让 X 的生成树的所有边都在 Fl + 1 层中就可以了。所以在开始搜索 X 的非树边前，我们先将 Tl 中在 X 中的边全部移动到 Tl + 1 中，并且在 Fl + 1中也加入这些边。

我们假设性质 2 在第 i 层成立，即第 i 层中所有连通分量的节点数为 ⌊n/2i⌋。第 i + 1 层中的连通分量只在将第 i 层的树边移动到第 i + 1 层中时改变，所以我们只要证明在移动过程中变化的连通分量的节点数最多为 ⌊n/2i + 1⌋ 即可。将第 i 层的树边移动到第 i + 1 层时，相当于在第 i + 1 层将一些小连通分量合并成一个点集等于 X 中的点集的连通分量，而由于 X 的节点数不超过 ⌊n/2i + 1⌋，所以第 i + 1 层中所有的连通分量的节点数都不超过 ⌊n/2i + 1⌋。所以性质 2 成立。

由于最大层数为 O(logn)，而且边的层号单调递增，层号不变时，边只会从非树边变成树边。所以每条边我们都只会操作 O(logn) 次。假如我们可以将每次操作的时间控制在 O(logn)，那么我们就得到了一个插入和删除的均摊时间为 O(log2n) 的算法。

从上面的描述中我们可以看到，对一条边时只有以下几种操作：

  1. 查询某点在 Fi 里的哪棵树中。

  2. 用这条边将两棵树连起来，或者将这条边删掉，得到两棵树。

  3. 将这条边加入到 Ni 中，或者从 Ni 中删掉。

  4. 将这条边加入到 Ti 中，或者从 Ti 中删掉。

  5. 遍历以 Fi 中指定子树里的节点为端点的 Ni 和 Ti 里的所有边。

其中，查询在哪棵树中，以及在森林里增删树边可以通过用 LCT 或者 ETT 来维护 Fi 实现 O(logn) 的均摊复杂度。

遍历与指定子树相连的 Ni 和 Ti 中的边时，显然不可以直接遍历这个子树的所有节点，这样每次找到一条边的最坏情况复杂度是 O(n) 的。注意到，我们只需要做到在 O(logn) 的时间内找到一条边即可。假如我们要遍历与指定子树相连的 Ni 里的边，并且我们用 LCT 来维护 Fi，那我们可以在 LCT 中维护 auxiliary tree 的每个子树内的任意一个存在某条 Ni 中的边与之相连的点的编号，将这个编号称为 tag。要找一条与原图中的指定子树相连的 Ni 中的边时，只需要从 auxiliary tree 的根节点中拿出 tag，假设是 u，然后找以 u 为端点的 Ni 中的点即可。

LCT 的节点只有指向 preferred child 的指针，没有指向 non-preferred children 的指针，但是维护子树信息需要从 non-preferred children 所在的子树的信息。通常这是通过 Top Tree 来实现的，即用 splay 来合并 non-preferred children 所在的子树的信息，然后通过根将合并后的信息传给节点（参考：https://www.cnblogs.com/Khada-Jhin/p/9743397.html）。但是这样代码量太大了。

注意到，我们其实不需要将所有 non-preferred children 所在的子树的信息合并起来，我们只需要从有 tag 的子树中随便选一个，就可以把它的 tag 作为当前节点的 tag 。所以我们只需要在每个节点用一个哈希表来维护所有有 tag 的 non-preferred children 的编号，更新节点 x 的 tag 的流程如下。

if (有边连着自己) {
	x.tag = x
} else if (x.left_child.tag != NIL) {
	x.tag = x.left_child.tag
} else if (x.right_child != NIL) {
	x.tag = x.right_child.tag
} else if (x.tagged_non_preferred_children is not empty) {
	c = x.tagged_non_preferred_children里的任意一个元素
	x.tag = c.tag
} else {
	x.tag = NIL
}

向 Ni 中插入边时，假如某个点 u 原先没有与之相连的 Ni 中的边，那就 access(u)，再将这条边插入到 Ni 中，从而保证 tag 都是有效的。同样，删除时，如果某个点 u 原先只有一条与之相连的 Ni 中的边，那就 access(u)，再将这条边从 Ni 中删掉。

动态图完全连通性截至2017年的最新成果汇总：https://www.cs.cmu.edu/~anupamg/advalgos17/handouts/italiano-talk-extract.pdf

其中这篇文章做到了 O(logn/logloglogn) 的连通性查询以及均摊复杂度为 O(logn(loglogn)3) 的更新：

Thorup M. Near-optimal fully-dynamic graph connectivity[C]//Proceedings of the thirty-second annual ACM symposium on Theory of computing. 2000: 343-350.

给我的个人博客打个广告：https://seekstar.github.io/2021/11/20/%E6%B4%9B%E8%B0%B7p5247-%E5%8A%A8%E6%80%81%E5%9B%BE%E5%AE%8C%E5%85%A8%E8%BF%9E%E9%80%9A%E6%80%A7-lct%E8%A7%A3%E6%B3%95/

题目链接：https://www.luogu.com.cn/problem/P5247

完整代码：

#include <iostream>
#include <unordered_set>
#include <stack>
#include <unordered_map>
#include <cstring>

using namespace std;

#define MAXN 5011
#define MAX_LEVEL 15

struct LCT {
	int c[MAXN][2], fa[MAXN], sta[MAXN];
	bool r[MAXN];
	// subtree_size2 is the sum of the sizes of non-preferred children's subtrees
	int subtree_size[MAXN], subtree_size2[MAXN];
	struct Tag {
		// Only stores edges of this level.
		unordered_set<int> edges;
		int tag;
		unordered_set<int> tagged_non_preferred_children;
	} tag_tree[MAXN], tag_non_tree[MAXN];

	void update_tag(Tag tags[], int x) {
		if (!tags[x].edges.empty()) {
			tags[x].tag = x;
		} else if (tags[ls(x)].tag) {
			tags[x].tag = tags[ls(x)].tag;
		} else if (tags[rs(x)].tag) {
			tags[x].tag = tags[rs(x)].tag;
		} else if (!tags[x].tagged_non_preferred_children.empty()) {
			tags[x].tag = tags[*tags[x].tagged_non_preferred_children.begin()].tag;
		} else {
			tags[x].tag = 0;
		}
	}
	void new_non_preferred_child(int x) {
		if (fa[x] == 0)
			return;
		subtree_size2[fa[x]] += subtree_size[x];
		if (tag_tree[x].tag)
			tag_tree[fa[x]].tagged_non_preferred_children.insert(x);
		if (tag_non_tree[x].tag)
			tag_non_tree[fa[x]].tagged_non_preferred_children.insert(x);
	}
	void delete_non_preferred_child(int x) {
		if (fa[x] == 0)
			return;
		subtree_size2[fa[x]] -= subtree_size[x];
		if (tag_tree[x].tag)
			tag_tree[fa[x]].tagged_non_preferred_children.erase(x);
		if (tag_non_tree[x].tag)
			tag_non_tree[fa[x]].tagged_non_preferred_children.erase(x);
	}

	inline int& ls(int rt) {
		return c[rt][0];
	}
	inline int& rs(int rt) {
		return c[rt][1];
	}
	inline bool not_splay_rt(int x) {
		return ls(fa[x]) == x || rs(fa[x]) == x;
	}
	inline int side(int x) {
		return x == rs(fa[x]);
	}
	void Init(int n) {
		// Initially every node is a tree by itself.
		// memset all to 0.
		for (int i = 1; i <= n; ++i) {
			subtree_size[i] = 1;
		}
	}
	inline void pushr(int x) {
		swap(ls(x), rs(x));
		r[x] ^= 1;
	}
	inline void pushdown(int x) {
		if (r[x]) {
			if (ls(x))
				pushr(ls(x));
			if (rs(x))
				pushr(rs(x));
			r[x] = false;
		}
	}
	inline void __pushup(int x) {
		update_tag(tag_tree, x);
		update_tag(tag_non_tree, x);
		subtree_size[x] = subtree_size[ls(x)] + subtree_size[rs(x)] + 1 + subtree_size2[x];
	}
	// At first x is not in its tagged_non_preferred_children
	inline void __pushup_splay_rt(int x) {
		__pushup(x);
		new_non_preferred_child(x);
		// No need to update tag[fa[x]], because if it was in this subtree, then it is still in this subtree.
	}
	// tag[x] is not updated.
	void __rotate_up(int x) {
		int y = fa[x], z = fa[y], side_x = side(x), w = c[x][side_x ^ 1];
		fa[x] = z;
		if (not_splay_rt(y))
			c[z][side(y)] = x;
		if (w)
			fa[w] = y;
		c[y][side_x] = w;
		fa[y] = x;
		c[x][side_x ^ 1] = y;
		__pushup(y);
	}
	// tag[x] is not updated.
	// The original splay root is removed from its father's tagged_non_preferred_children.
	void __splay(int x) {
		int y = x, top = 0;
		while(1) {
			sta[++top] = y;
			if (!not_splay_rt(y))
				break;
			y = fa[y];
		}
		int to = fa[y];
		delete_non_preferred_child(y);
		while (top)
			pushdown(sta[top--]);
		while (fa[x] != to) {
			int y = fa[x];
			if (fa[y] != to)
				__rotate_up(side(x) == side(y) ? y : x);
			__rotate_up(x);
		}
	}
	void splay(int x) {
		__splay(x);
		__pushup_splay_rt(x);
	}
	void access(int x) {
		int ori_x = x;
		for (int w = 0; x; w = x, x = fa[x]) {
			__splay(x);
			delete_non_preferred_child(w);
			new_non_preferred_child(rs(x));
			rs(x) = w;
			__pushup_splay_rt(x);
		}
		__splay(ori_x);
		__pushup(ori_x);
	}
	int find_root(int x) {
		access(x);
		for (; ls(x); x = ls(x))
			pushdown(x);
		__splay(x);
		__pushup(x);
		return x;
	}
	inline void make_root(int x) {
		access(x);
		pushr(x);
	}
	void __link(int x, int y) {
		// If simply fa[x] = y, the complexity might be wrong.
		access(y);
		pushdown(x);
		fa[y] = x;
		ls(x) = y;
		__pushup(x); // Might be unnecessary
	}
	inline void link_new(int x, int y) {
		make_root(x);
		__link(x, y);
	}
	inline void link(int x, int y) {
		make_root(x);
		if (find_root(y) == x)
			return;
		__link(x, y);
	}
	inline void split(int x, int y) {
		make_root(x);
		access(y);
	}
	void cut_existing(int x, int y) {
		split(x, y);
		fa[x] = ls(y) = 0;
		__pushup(y); // Might be unnecessary
	}
	void cut(int x, int y) {
		split(x, y);
		if (ls(y) != x || rs(x) != 0)
			return;	// No such edge (x, y)
		fa[x] = ls(y) = 0;
		__pushup(y); // Might be unnecessary
	}
	std::unordered_set<int> take_out_edges(Tag type[], int x) {
		access(x);
		auto tmp = std::unordered_set<int>();
		swap(tmp, type[x].edges);
		update_tag(type, x);
		return std::move(tmp);
	}
	void add_directed_edge(Tag type[], int x, int y) {
		if (type[x].edges.empty()) {
			access(x);
			type[x].edges.insert(y);
			update_tag(type, x);
		} else {
			type[x].edges.insert(y);
		}
	}
	void delete_directed_edge(Tag type[], int x, int y) {
		if (type[x].edges.size() == 1) {
			access(x);
			type[x].edges.erase(y);
			update_tag(type, x);
		} else {
			type[x].edges.erase(y);
		}
	}
	void new_tree_edge(int x, int y) {
		link_new(x, y);
		add_directed_edge(tag_tree, x, y);
		add_directed_edge(tag_tree, y, x);
	}
};

struct DynamicConnectivity {
	struct LCT F[MAX_LEVEL];
	unordered_map<int, unordered_map<int, int> > level;
	void Init(int n) {
		for (int i = 0; (1 << i) <= n; ++i)
			F[i].Init(n);
	}
	// Assume no duplicate edge
	void link_new(int x, int y) {
		level[x][y] = 0;
		level[y][x] = 0;
		if (F[0].find_root(x) == F[0].find_root(y)) {
			F[0].add_directed_edge(F[0].tag_non_tree, y, x);
			F[0].add_directed_edge(F[0].tag_non_tree, x, y);
		} else {
			F[0].new_tree_edge(x, y);
		}
	}
	bool reconnect(int x, int y, int l) {
		F[l].access(x);
		F[l].access(y);
		if (F[l].subtree_size[x] > F[l].subtree_size[y])
			swap(x, y);
		while (1) {
			F[l].access(x);
			int u = F[l].tag_tree[x].tag;
			if (u == 0)
				break;
			auto tmp = F[l].take_out_edges(F[l].tag_tree, u);
			for (int v : tmp) {
				F[l].delete_directed_edge(F[l].tag_tree, v, u);
				F[l+1].new_tree_edge(u, v);
				++level[u][v];
				++level[v][u];
			}
		}

		y = F[l].find_root(y);
		while (1) {
			F[l].access(x);
			int u = F[l].tag_non_tree[x].tag;
			if (u == 0)
				break;
			auto tmp = F[l].take_out_edges(F[l].tag_non_tree, u);
			do {
				auto it = tmp.begin();
				int v = *it;
				tmp.erase(it);
				F[l].delete_directed_edge(F[l].tag_non_tree, v, u);
				if (F[l].find_root(v) == y) {
					if (!tmp.empty()) {
						F[l].access(u);
						swap(tmp, F[l].tag_non_tree[u].edges);
						F[l].update_tag(F[l].tag_non_tree, u);
					}
					for (int i = 0; i < l; ++i)
						F[i].link_new(u, v);
					F[l].new_tree_edge(u, v);
					return true;
				} else {
					F[l+1].add_directed_edge(F[l+1].tag_non_tree, u, v);
					F[l+1].add_directed_edge(F[l+1].tag_non_tree, v, u);
					++level[u][v];
					++level[v][u];
				}
			} while (!tmp.empty());
		};
		return false;
	}
	void cut_existing(int x, int y) {
		auto it1 = level[x].find(y);
		int l = it1->second;
		level[x].erase(it1);
		level[y].erase(x);

		auto& s = F[l].tag_non_tree[x].edges;
		if (s.find(y) != s.end()) {
			F[l].delete_directed_edge(F[l].tag_non_tree, x, y);
			F[l].delete_directed_edge(F[l].tag_non_tree, y, x);
			return;
		}
		F[l].delete_directed_edge(F[l].tag_tree, x, y);
		F[l].delete_directed_edge(F[l].tag_tree, y, x);
		for (int i = 0; i <= l; ++i)
			F[i].cut_existing(x, y);
		while (1) {
			if (reconnect(x, y, l))
				break;
			if (l == 0)
				break;
			--l;
		}
	}
	bool is_connected(int x, int y) {
		return F[0].find_root(x) == F[0].find_root(y);
	}
};

int main() {
	int n, m;
	static DynamicConnectivity dc;

	scanf("%d%d", &n, &m);
	dc.Init(n);
	int last = 0;
	while (m--) {
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		x ^= last;
		y ^= last;
		switch (op) {
		case 0:
			dc.link_new(x, y);
			break;
		case 1:
			dc.cut_existing(x, y);
			break;
		case 2:
			if (dc.is_connected(x, y)) {
				puts("Y");
				last = x;
			} else {
				puts("N");
				last = y;
			}
			break;
		}
	}

	return 0;
}
洛谷 P2147 [SDOI2008] 洞穴勘测 ETT解法
luogu P4332 [SHOI2014]三叉神经树 LCT