CF1391E Pairs of Pairs 题解

题意：

给出一张无向连通图，选择以下任意一个任务完成：

找到图中一条至少包含 \(\lceil \frac {n} {2} \rceil\) 个点的简单路径。

找到图中偶数（至少 \(\lceil \frac {n} {2} \rceil\) ）个点，满足任意两个点对包含的 \(4\) 个点的导出子图至多存在 \(2\) 条边。

若完成任务 \(1\)，则输出 PATH，并输出简单路径包含的点数与该路径依次经过的点。

若完成任务 \(2\)，则输出 PAIRING，并输出选出的点对数及每一组点对。

可以证明，符合条件的一张图一定可以完成其中一个任务。

输入格式：

每个测试包含多个测试用例。

第一行包含测试用例的数量 \(t~(1 \le t \le 10^5)\) 。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 \(n, m~(2 \le n \le 5 \times 10^5,1 \le m \le 10^6)\)，分别表示节点数和边数。

接下来的 \(m\) 行，每行包含两个整数 \(u\) 和 \(v~(1 \le u, v \le n,~u \neq v)\)，表示给定图中节点 \(u\) 和 \(v\) 之间存在一条无向边。

保证给定的图是连通的且简单的，不包含同一对节点之间的多条边，也不含有自环。

保证所有测试用例中 \(n\) 的总和不超过 \(5 \times 10^5\)。保证所有测试用例中 \(m\) 的总和不超过 \(10^6\)。

输出格式：

对于每个测试用例，输出格式如下：

如果找到了一种配对，首先输出 PAIRING。

然后，输出 \(k~(\lceil \frac{n}{2} \rceil \le 2k \le n)\)，表示配对中的对数。

然后，在接下来的 \(k\) 行中，输出两个整数 \(a\) 和 \(b\) ，表示 \(a\) 和 \(b\) 被配对在一起。

请注意，图中不一定有 \(a\) 和 \(b\) 之间的边！

这种配对必须是有效的，并且每个节点最多只能属于一个配对。

否则，如果找到了一条路径，首先输出 PATH。

然后，输出 \(k~(\lceil \frac{n}{2} \rceil \le k \le n)\)，表示路径中节点的数量。

然后，在第二行中，按照路径上的顺序输出 \(k\) 个整数 \(v_1, v_2, \ldots, v_k\)。

形式上，对于每个 \(i~(1 \le i < k)\)，\(v_i\) 和 \(v_{i+1}\) 应该有一条边连接。

这条路径必须是简单的，意味着每个节点不应重复出现。

原题这翻译不写简单图可还行？

考虑构建原图的 dfs 树，那么只要存在深度大于等于 \(\left\lceil \frac{n}{2} \right\rceil\) 的节点，把它到根的树上路径输出即可。

否则我们将每一层的节点两两配对，如果有奇数个就随便扔掉一个。

下面来证明这样做的正确性。设 \(a,b\) 和 \(c,d\) 分别是两层的某两个节点，且 \(d_a < d_c\) ，\(d\) 表示深度。

若 \(a,b\) 分别为 \(c,d\) 的父亲，他们的导出子图仅包括两条树边。
若 \(a,b\) 中的某一个是 \(c,d\) 的父亲，同样只有两条树边。
若 \(a,b\) 和 \(c,d\) 没什么特别地树上关系，那最多也只有两条返祖边。

正确性得证。那么这题就做完了。

时间复杂度 \(\mathcal{O}(n+m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(1e6 + 15))

vector<int> vec[N], vec2[N];
int cnt, pos, mxdep, ans1[N], ans2[N], dep[N], fa[N];
void dfs(int u)
{
    dep[u] = dep[fa[u]] + 1; vec2[dep[u]].pb(u);
    if(dep[u] >= mxdep) { mxdep = dep[u], pos = u; }
    for(auto v : vec[u]) if(!dep[v]) { fa[v] = u, dfs(v); }
}
void solve()
{
    int n, m; cin >> n >> m; mxdep = pos = cnt = 0;
    rep(i, 0, n + 5) { dep[i] = fa[i] = 0, vec[i].clear(); vec2[i].clear(); }
    rep(i, 1, m) { int u, v; cin >> u >> v; vec[u].pb(v); vec[v].pb(u); }
    dfs(1);
    for(int i = 1; i <= mxdep; i++)
        for(int j = 0; j + 1 < vec2[i].size(); j += 2) {
            ++cnt; ans1[cnt] = vec2[i][j]; ans2[cnt] = vec2[i][j + 1];
        }
    if((cnt * 2) >= (n + 1) / 2)
    {
        cout << "PAIRING" << '\n' << cnt << '\n';
        rep(i, 1, cnt) cout << ans1[i] << ' ' << ans2[i] << '\n';
    }else
    {
        cout << "PATH" << '\n'; cnt = 0;
        while(pos) { ans1[++cnt] = pos, pos = fa[pos]; }
        cout << cnt << '\n'; rep(i, 1, cnt) cout << ans1[i] << " \n"[i == cnt];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}