题解 CF1391E 【Pairs of Pairs】

· · 题解

题意

请你完成以下两个子问题的任意一个：

1.给至少 \lceil \frac{n}{2} \rceil 个节点两两配对，使得任意两对点的导出子图不多于2条边。

2.找一条长度为 \lceil \frac{n}{2} \rceil 的简单路径。

题解

发现任务 2 看起来比较容易：我们构建出图的 dfs 树，求出每个点的深度，如果深度 \geq\lceil \frac{n}{2}\rceil 的点存在，我们就把这个点到根（根直接钦定为 1 ）的路径拎出来输出就行了。

考虑任务 1 怎么做：我们把同一深度的点两两配对，因为同一深度的点之间是不会有连边的。然后由于dfs树有个性质就是非树边连接的两点必然是祖孙关系，所以考虑任意选 (a1,a2),(b1,b2) 这两对点，假设 deep_{a1}<deep_{b1} 那么他们之间的边只有这几种情况：

所以肯定是符合要求的。

代码


#include <cstdio>
#include <vector>
const int N = 1000005;
int h[N], nxt[N << 1], adj[N << 1], n, m, T, t, u, v, fa[N], d[N], o1[N], o2[N], mxd, id;
std::vector<int> g[N];
inline void add() { nxt[++t] = h[u], h[u] = t, adj[t] = v, nxt[++t] = h[v], h[v] = t, adj[t] = u; }
inline void dfs(int x) {
    g[d[x] = d[fa[x]] + 1].push_back(x);
    if (d[x] >= mxd) mxd = d[x], id = x;
    for (int i = h[x], j; i; i = nxt[i])
        if (!d[j = adj[i]])
            fa[j] = x, dfs(j);
}
int main() {
    scanf("%d", &T);
    int i, j, co;
    while (T--) {
        scanf("%d%d", &n, &m),co = mxd = id = t = 0;
        for (i = 1; i <= n; ++i) d[i] = h[i] = fa[i] = 0, g[i].clear();
        while (m--) scanf("%d%d", &u, &v), add();
        dfs(1);
        for (i = 1; i <= mxd; ++i)
            for (j = 0; j + 1 < g[i].size(); j += 2) 
                o1[++co] = g[i][j], o2[co] = g[i][j + 1];
        if ((co << 1) >= (n + 1 >> 1)) {
            puts("PAIRING"), printf("%d\n", co);
            for (i = 1; i <= co; ++i) printf("%d %d\n", o1[i], o2[i]);
            continue;
        }
        puts("PATH"),co = 0;
        while (id) o1[++co] = id, id = fa[id];
        printf("%d\n", co);
        for (i = 1; i <= co; ++i) printf("%d ", o1[i]);
        puts("");
    }
    return 0;
}