P11726 题解

并非图论建模。

实为暴力模拟。

对于

v \in [1,n]

新建一个仅包含

v

的双向链表。

定义双向链表的「表头」为其中连接至少一个空节点的节点。

对于一对

a_i,b_i

交换时：

若 $a_i,b_i$ $a_{i}, b_{i}$ 在同一个链表 $T$ $T$ 内：
- 若 $a_i,b_i$ 在 $T$ 中不相邻：输出No，结束程序。
- 若 $a_i,b_i$ 相邻：交换 $a_i,b_i$ 。
若 $a_i,b_i$ $a_{i}, b_{i}$ 不在同一链表内：考虑合并 $a_i,b_i$ $a_{i}, b_{i}$ 所在链表。
- 若 $a_i$ 或 $b_i$ 不为其所在链表「表头」：输出No，结束程序。
- 若 $a_i,b_i$ 均为其所在链表「表头」：连接 $a_i,b_i$ ，然后交换 $a_i,b_i$ 。

如未结束程序，输出Yes并输出方案。

如何判断

a_i,b_i

是否相邻？直接在链表上查找即可。

如何判断

a_i,b_i

是否在同一链表上？使用并查集维护。

有关代码中exchange操作的形象化理解可见下图。

代码：

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 500120;

int c[N][2];
bool v[N];
//#define empty(a) (c[a][0] == 0 && c[a][1] == 0)
#define spare(a) (c[a][0] == 0 || c[a][1] == 0) // 判断 a 是否为「表头」，是为true
#define full(a) (c[a][0] != 0 && c[a][1] != 0) // 判断 a 是否为「表头」，否为true
#define found(a, b) (c[a][0] == b || c[a][1] == b) // 判断 a 是否与 b 相邻
#define check(a, b) (c[a][1] == b) // 求 b 在 a 的哪一个指针上 
#define canfill(a) check(a, 0) // 求 a 连接空节点的指针 
// *** 并非指针（bushi 
inline void exchange(int a, int b) // 链表交换操作 
{
	int w1 = check(a, b), w2 = check(b, a), x;
	if (c[a][!w1] != 0)
	{
		x = c[a][!w1];
		c[x][check(x, a)] = b;
	}
	if (c[b][!w2] != 0)
	{
		x = c[b][!w2];
		c[x][check(x, b)] = a;
	}
	c[b][w2] = c[a][!w1];
	c[a][w1] = c[b][!w2];
	c[b][!w2] = a;
	c[a][!w1] = b;

}
void Dfs(int x, int z) // 遍历链表 
{
	cout << x << '\n';
	v[x] = true;
	for (int i = 0; i < 2; ++i)
		if (c[x][i] != 0 && c[x][i] != z)
			Dfs(c[x][i], x);
}
// *** 上面的 if 本可以写成 (!v[c[x][i]])，但先前作者写出了环 XD 
// *** 所以用了这个判断以迅速判断是否出现环（及其他的奇形怪状 

int f[N], sz[N];
inline void Init(int n) // 并查集初始化 
{
	iota(f + 1, f + n + 1, 1);
	fill(sz + 1, sz + n + 1, 1);
}
int Find(int x) // 路径压缩 
{
	return x == f[x] ? x : (f[x] = Find(f[x]));
}
inline bool Merge(int x, int y) // （启发式）合并 
{
	x = Find(x), y = Find(y);
	if (x == y)
		return false; // 已在同一链表上 
	if (sz[x] < sz[y])
		swap(x, y);
	f[y] = x;
	sz[x] += sz[y];
	return true; // 可以合并 
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	Init(n);
	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		cin >> a >> b;
		if (!Merge(a, b)) // 如果 a_i, b_i 在同一链表上 
		{
			if (!found(a, b)) // 如果 a_i, b_i 不相邻 
			{
				cout << "No\n";
				return 0;
			}
			else // 如果 a_i, b_i 相邻 
			{
				exchange(a, b);
			}
		}
		else // 如果 a_i, b_i 不在同一链表上 
		{
			if (full(a) || full(b)) // 如果 a_i 或 b_i 不是「表头」 
			{
				cout << "No";
				return 0;
			}
			else // 如果 a_i, b_i 均为「表头」 
			{
				int w1 = canfill(a), w2 = canfill(b);
				c[a][w1] = b;
				c[b][w2] = a;
				exchange(a, b);
			}
		}
	}
	// 输出方案 
	cout << "Yes\n";
	for (int i = 1; i <= n; ++i)
		if (spare(i) && !v[i]) // 找尽可能小的「表头」 遍历
			Dfs(i, 0);
	return 0;
}

文章操作

相关推荐

评论

P11726 题解