CF566E Restoring Map 题解

CF566E Restoring Map

题意

• 有一棵 $n$ 个点的树，你不知道这棵树的边是怎么连的。
• 你得到了 $n$ 条关于每个点信息，每条信息记录了距离某一个点 $\le 2$ 的所有点。
• 但你不知道每条信息具体是哪个点的。
• 你需要构造一棵满足这些信息的树。
• $n \le 10^3$。

题解

我们将叶子节点定义为度数为 $1$ 的节点，非叶节点定义为度数 $>1$ 的节点。

首先我们来考虑大部分情况，即至少有三个非叶节点的情况。

在这种情况下，两个非叶节点 $(x,y)$ 之间存在边，当且仅当存在两个集合的交为 $\\{x,y\\}$。

于是可以得到所有非叶节点之间的连边，bitset 优化即可做到 $\mathcal O(\frac{n^3}w)$。

值得一提的是，如果当存在两个集合的交集大小为 $2$ 时，对 bitset 暴力 for 循环找值为 $1$ 的位置，复杂度并不会除以那个 $w$，是错的，可以被卡掉，但不知道为什么 CF 没有卡，也许是因为 CF 评测机太快了。正确的写法是借用 _Find_first() 和 _Find_next() 函数，前者是找到 bitset 中从低位到高位第一个 $1$ 的位置，后者是找到当前位置的下一个为 $1$ 的位置，这样复杂度才会除以那个 $w$。

现在，我们知道每个点是否为叶子节点，接下来考虑如何找到叶子节点在树中的父亲。

显然，对于每个叶子节点，在所有包含它的集合中，节点数最少的集合一定就是此叶子节点的集合。因此我们可以确定每个叶子节点对应的集合是哪个。

如果我们把连边集合定义为一个非叶节点与和它相连的非叶节点构成的集合，可以发现，一个叶子节点的集合中去掉所有叶子节点等于其父亲的连边集合，而所有非叶节点的连边集合一定互不相同，那么我们就可以确定所有叶子节点的父亲了，这里同样可以 bitset 优化。

最后来考虑非叶节点数量少于三个的情况。

如果不存在非叶节点，则 $n=2$，可以直接判掉。

如果只有一个非叶节点，那就意味着所有集合都是 $\{1,2,\cdots n\}$，也可以直接判掉。

如果有两个非叶节点，我们先采用至少三个非叶节点的方法找到这两个非叶节点，然后会发现这两个非叶节点的连边集合是一样的。但是，这个时候叶子的集合就只有两种，选其中一种里的叶子挂在一个非叶节点下，另一种里的叶子挂在另外一个非叶节点下就好了。

总时间复杂度 $\mathcal O(\frac{n^3}w)$。

代码

const int N = 1e3 + 7;
int n, v[N], w[N], cnt;
bitset<N> a[N], b[N], e[N];

int main() {
	rd(n);
	if (n == 2) return prints("1 2"), 0;
	bool ok = 1;
	for (int i = 1, j, k; i <= n; i++) {
		rd(k);
		if (k != n) ok = 0;
		while (k--) rd(j), a[i][j] = 1;
	}
	if (ok) {
		for (int i = 1; i < n; i++) print(n, ' '), print(i);
		return 0;
	}
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) {
			bitset<N> o = a[i] & a[j];
			if (o.count() != 2) continue;
			int x = o._Find_first(), y = o._Find_next(x);
			if (e[x][y]) continue;
			print(x, ' '), print(y);
			e[x][y] = e[y][x] = 1, v[x] = v[y] = 1;
		}
	for (int i = 1; i <= n; i++)
		if (!v[i]) {
			int s = n + 1, o = 0;
			for (int j = 1; j <= n; j++)
				if (!w[j] && a[j][i]) {
					int c = a[j].count();
					if (c < s) s = c, o = j;
				}
			b[i] = a[o], w[o] = 1;
		} else e[i][i] = 1, ++cnt;
	if (cnt == 2) {
		int x, y;
		for (int i = 1; i <= n; i++)
			if (v[i]) x = i;
		for (int i = n; i; i--)
			if (v[i]) y = i;
		for (int i = 1; i <= n; i++)
			if ((int)a[i].count() != n) {
				for (int j = 1; j <= n; j++) {
					if (v[j]) continue;
					if (a[i][j]) print(x, ' ');
					else print(y, ' ');
					print(j);
				}
				break;
			}
		return 0;
	}
	for (int i = 1; i <= n; i++)
		if (!v[i]) {
			for (int j = 1; j <= n; j++)
				if (!v[j]) b[i][j] = 0;
			for (int j = 1; j <= n; j++)
				if (v[j] && b[i] == e[j]) {
					print(i, ' '), print(j);
					break;
				}
		}
	return 0;
}