CF1391E 题解

题意

给定一个无向图，从下面两个操作中选择一个完成：

• 输出一条长度不小于 $\lceil \frac{n}{2} \rceil$ 的链
• 选出至少 $\lceil \frac{n}{2} \rceil$ 个点，两两组成点对，使得任意两个点对 $4$ 个点的子图边数不超过 $2$。

题解

构造题，求出无向图的一个 $\tt{dfs}$ 树，若存在点深度大于等于 $\lceil \frac{n}{2} \rceil$，直接输出这个点到根节点的路径；否则考虑构造点对。

在 $\tt{dfs}$ 树上同层的点，在原图中是没有边相连的（如果有就会变成子树），因此将所有点和与其同层的点组成点对即可，这样边数不会超过 $2$，而深度是小于 $\lceil \frac{n}{2} \rceil$ 的，就算每层都剩一个点选出的点数也不会小于 $\lceil \frac{n}{2} \rceil$，所以这样构造一定有解。

CODE

#include <bits/stdc++.h>
using namespace std;

inline int read();
#define N 500010
#define pb push_back

int n, m, dep[N], f[N], vis[N];
vector<int> e[N], vec[N];

void dfs(int x, int fa) {
	vis[x] = 1, dep[x] = dep[fa] + 1, f[x] = fa;
	for (auto y : e[x]) if (!vis[y]) dfs(y, x);
}

int main() {
	for (int T = read(); T --; ) {
		n = read(), m = read();
		for (int i = 1; i <= m; i ++) {
			int x = read(), y = read();
			e[x].pb(y), e[y].pb(x);
		}

		dfs(1, 0);
		int flag = 0, sum = 0, x = 0;
		for (int i = 1; i <= n; i ++) {
			if (dep[i] * 2 >= n) flag = 1, x = i;
		}

		if (flag) {
			printf("PATH\n%d\n", dep[x]);
			for (; x; x = f[x]) printf("%d ", x);
			puts("");
		} else {
			for (int i = 1; i <= n; i ++) {
				vec[dep[i]].pb(i);
			}
			for (int i = 1; i <= n; i ++) {
				if (vec[i].size() % 2 == 1) sum ++;
			}
			printf("PAIRING\n%d\n", (n - sum) / 2);
			for (int i = 1; i <= n; i ++) {
				for (int j = 0; j < vec[i].size() / 2; j ++) {
					printf("%d %d\n", vec[i][j * 2], vec[i][j * 2 + 1]);
				}
			}
		}

		for (int i = 1; i <= n; i ++) {
			vec[i].clear(), e[i].clear();
			f[i] = dep[i] = vis[i] = 0;
		}
	}
	return 0;
}

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}