P11726 题解

· · 题解

并非图论建模。

实为暴力模拟。

对于 v \in [1,n] 新建一个仅包含 v 的双向链表。

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

对于一对 a_i,b_i 交换时：

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

如何判断 a_i,b_i 是否相邻？直接在链表上查找即可。

如何判断 a_i,b_i 是否在同一链表上？使用并查集维护。

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

代码：

#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;
}