P10179 水影若深蓝 题解

· · 题解

P10179 水影若深蓝 题解

前言

赛时感觉还算简单的一道有点意思的构造，个人感觉只有黄题难度（

题意简述

要求构造一棵有 n 个结点的树，需满足 m 个 u_i 个 v_i 在树上的唯一简单路径恰含两条边的条件。

条件转化

令树为有根树，则不难发现，一个条件等同于让 u 和 v 共父亲，或者其中一个为另一个的父亲之父亲。此处先假设 u 和 v 有同一个父亲，因为二种情况在无根树中是等价的。第二种情况在最后满足树根唯一时使用即可。

满足条件的构造

两个结点共父亲的关系显然是具有传递性的，可以考虑用并查集维护相同父亲的结点们。

在根据所有条件得到最终并查集后，根据共父亲的条件，n 个结点可以分成几部分，这里将其称为“层”。

那么对于第 i 和 i + 1 层，可以让第 i 层任一结点成为 i+1 层所有结点的父亲。那么最终可能得到一个森林，因为除了第一层，其他层结点都有且仅有一个父亲。

此时再来考虑条件的第二种转化。不难想到可以让第二层的某个结点作为树根，此时其到其原先所在的层的路径中仍有两条边。但如果仅有一层且该层结点不止一个，是没有办法得到树的，那么判定为无解。至此构造结束。

代码

并查集在代码中采用路径压缩的优化，未使用启发式合并，处理条件的最坏时间复杂度 O(m\log n)。最终构造的方案可以 O(n) 得到。

同时，对于此类传递关系也可以通过生成无向图并 dfs 寻找连通块维护，复杂度线性。该种方法可以参考我的另一篇题解 P9869 三值逻辑 题解。

# include <cstdio>
# include <vector>

using namespace std;

vector<int> father;  // 并查集

int find(int x) {
    return (x == father[x]) ? x : (father[x] = find(father[x]));  // 路径压缩的并查集
}

int main() {
    int T;
    scanf("%d", &T);

    for (int c1 = 0; c1 < T; ++c1) {
        int n, m;
        scanf("%d %d", &n, &m);

        father = vector<int>(n);
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }  // 并查集的初始化

        for (int c2 = 0; c2 < m; ++c2) {
            int u, v;
            scanf("%d %d", &u, &v);
            u -= 1;  // 个人习惯下标从 0 开始使用 QwQ
            v -= 1;

            father[find(v)] = find(u);
        }  // 对条件的维护

        int layerNum = 0;
        vector<vector<int>> layers1(n);  // layers1[x] 表示并查集中以 x 作为代表的集合（层）

        for (int i = 0; i < n; ++i) {
            layerNum += find(i) == i;
            layers1[father[i]].push_back(i);
        }

        if (layerNum <= 1) {
            printf("No\n");  
            continue;
        } else {
            printf("Yes\n");
        }

        // 为方便构造，将 layers1 根据代表编号的方式改为存储每一层的内含结点，从而数组中没有元素是空数组
        vector<vector<int>> layers2; 
        for (int i = 0; i < n; ++i) {
            if (layers1[i].empty()) {
                continue;
            }

            layers2.push_back(layers1[i]);
        }

        int root = layers2[1].back();
        layers2[1].pop_back();
        for (int node: layers2[0]) {
            printf("%d %d\n", root + 1, node + 1);
        }

        bool jump = layers2[1].empty();  // 特判一下如果第二层的结点被用来当根后第二层没有结点了，那么给出构造时跳过该层
        for (int i = 0; i < layerNum - 1; ++i) {
            if (jump && (i == 0) && (layerNum > 2)) {
                for (int j = 0; j < layers2[2].size(); ++j) {
                    printf("%d %d\n", layers2[0][0] + 1, layers2[2][j] + 1);
                }

                i += 1;
                continue;
            }
            for (int j = 0; j < layers2[i + 1].size(); ++j) {
                printf("%d %d\n", layers2[i][0] + 1, layers2[i + 1][j] + 1);
            }
        }
    }

    return 0;
}