自动搬运

查看原文

来自洛谷，原作者为

	zhylj 人生输家

搬运于2025-08-24 22:25:31，当前版本为作者最后更新于2021-10-28 19:29:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑树的情况如何构造：

我们考虑从叶子开始由深至浅合并子树，我们让三种颜色分别代表三个意义：

• 颜色 $1$：与这个点相邻的边均已建好。
• 颜色 $2$：以这个点为根的整个子树都已建好，但它和它的父亲还未连边。
• 颜色 $3$：以这个点为根的整个子树还没建好。

显然，一开始所有点的颜色都要设为 $3$，然后我们按深度从大到小考虑每个点 $u$，将其和其所有孩子 $v$ 连边，完成这棵子树的构造，由于我们考虑的顺序，所以此时其所有孩子的颜色均为 $2$。故可以依次进行以下的步骤：

• 将 $u,v$ 合并。
• 连接所有颜色 $3$ 和颜色 $2$ 的点。
• 将颜色 $2$ 改为颜色 $1$。

在考虑完所有孩子后，我们就可以将 $u$ 的颜色 $3$ 改为颜色 $2$ 了。

接下来我们考虑仙人掌的构造：找出一棵 DFS 树，那么就有：每条边只被至多一个非树边覆盖、每条非树边均为返祖边。于是考虑利用颜色 $4$ 表示还未连返祖边的点。

那么在考虑点 $u$ 时，其所有孩子 $v$ 一共有三种情况（注意在每次拼接开始时，$u,v$ 分别都为连通块中唯一的颜色为 $3,2$ 的点）：

• $v$ 不在环中或 $v$ 所在的环的顶端深度大于 $u$：该情况子树中必然不存在颜色 $4$ 的点，可以和树的情况一样做。
• $v$ 在环中，且 $v$ 所在环的顶端深度等于 $u$：在做完树的情况后，把 $u$ 连向所有颜色为 $4$ 的点，再把所有颜色为 $4$ 的点变为 $1$。
• $v$ 在环中，且 $v$ 所在环的顶端深度小于 $u$：此情况 $v$ 的颜色应该被设为 $4$，但为了防止干扰前一种情况，我们应该把这种情况留到最后去处理（显然此时不存在任何颜色为 $4$ 的点）。

然后就做完了，操作数是 $\mathcal O(n)$ 的，较为宽裕。

const int N = 1e6 + 5;
 
int n, o_cnt;
char opt[N][20];
 
std::vector <int> E[N];
void Add(int u, int v) {
	E[u].push_back(v);
	E[v].push_back(u);
}
 
int dep[N], fa[N], low[N];
bool is_bg[N];
std::vector <int> ch[N], dfa;
void Dfs(int u) {
	dep[u] = dep[fa[u]] + 1;
	low[u] = dep[u];
	for(int v : E[u])
		if(v != fa[u]) {
			if(!dep[v]) {
				ch[u].push_back(v);
				fa[v] = u; Dfs(v);
				low[u] = std::min(low[u], low[v]);
			} else if(dep[v] < dep[u]) {
				low[u] = std::min(low[u], dep[v]);
				is_bg[u] = true;
			}
		}
	dfa.push_back(u);
}
void Solve() {
	for(int u : dfa) {
		sprintf(opt[++o_cnt], "r %d 1 3", u);
		std::sort(ch[u].begin(), ch[u].end(), [&](const int &x, const int &y) {
			return low[x] > low[y];
		});
		for(int v : ch[u]) {
			sprintf(opt[++o_cnt], "j %d %d", u, v);
			sprintf(opt[++o_cnt], "c %d 2 3", u);
			if(low[v] < dep[u] && is_bg[v]) {
				sprintf(opt[++o_cnt], "r %d 2 4", v);
			} else {
				if(low[v] == dep[u]) {
					sprintf(opt[++o_cnt], "c %d 3 4", u);
					sprintf(opt[++o_cnt], "r %d 4 1", u);
				}
				sprintf(opt[++o_cnt], "r %d 2 1", v);
			}
		}
		sprintf(opt[++o_cnt], "r %d 3 2", u);
	}
}
 
int main() {
	int m; scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		int k; scanf("%d", &k);
		std::vector <int> p;
		while(k--) { int x; scanf("%d", &x); p.push_back(x); }
		for(int j = 0; j < (int)p.size() - 1; ++j)
			Add(p[j], p[j + 1]);
	}
	Dfs(1);
	Solve();
	printf("%d\n", o_cnt);
	for(int i = 1; i <= o_cnt; ++i)
		printf("%s\n", opt[i]);
	return 0;
}