CF1695E Ambiguous Dominoes

如下图，给定 \(n\) 个 \(1\times 2\) 的多米诺骨牌，每个骨牌两边均写有数字，求一种矩形的构造方案，使得存在 \(2\) 种不同的方法将多米诺放进矩形中，使得不存在 \((x_1,y_1)\) 和 \((x_2,y_2)\) 满足：在 \(2\) 种方案中它们均在同一个多米诺中。 \(n\leq 3\times 10^5\) 。

首先考虑建图，将每个 \(x_i,y_i\) 连双向边，那么就将 \(n\) 个多米诺抽象成了 \(n\) 条边。很容易发现，当存在一个连通块使得该连通块中有且仅有 \(1\) 条边，那么该情况将无解。

考虑如何构造出一个方案，首先对于每个连通块进行一次 dfs ，记录下每个节点出现的地方，但是细节却不太一样：

对于每个第一次访问的节点遍历每条边，若这条边被经过则不去向下一个节点，否则去向，并在返回后重新将该节点放入答案。

对于每个不是第一次被访问的节点，直接记录一次并返回。

这里放个代码，其中 qwq 是用一个 vector 来记录每个节点， ncnt 用来记录当前连通块的编号。

void dfs(int x){
	qwq[ncnt].push_back(x);
	if(vis[x])
		return;
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		if(book[i>>1])
			continue;
		book[i>>1]=1;
		dfs(e[i].to);
		qwq[ncnt].push_back(x);
	}
}

然后就会发现一个很有趣的事实，就是这个序列长度为 \(2\times k+1\) ，其中 \(k\) 表示连通块中边的个数。这是因为在上述 dfs 的过程中dfs 树上的每一条边都被经过了一次，产生的 \(2\) 的贡献，而一开始时还经过了 dfs 树的根节点，所以是 \(2\times k+1\) 。

更有意思的是，第一个节点和最后一个节点一定相同，都是根，当对 qwq[ncnt].pop_back() 之后就会得到一个长度为 \(2\times k\) 的序列。将序列连成环则可以发现环上的每个 \((i,i+1)\) 都构成了原图上的一条边（因为这是在 dfs 树上），并且每条边都出现了 \(2\) 次（因为在进 dfs 树和出 dfs 树时都会出现一次）。最后有一个我不太会证的结论，即每条边出现的地方奇偶性不同。（有兴趣的可以参考官方题解）

那么接下来就可以利用这些结论了：对于每个连通块将 dfs 得到的 qwq 数组按照顺时针（逆时针也行）绕成一个环（放到网格上是 \(2\times k\) 的一段），那么取环上奇偶性不同的 \(2\) 个点得到的 \(2\) 种方案即为答案（可以参考下图进行理解），那么答案就是将所有连通块的网格都合并一下就好了。