任取一颗 \(\text{DFS}\) 树。
如果最大深度 \(\geq\frac{n}{k}\)，则找到了一条路径。
对于剩下的情况，我们按环去处理。钦定一个合法环中的“代表点”为 \(k\) 个环中只出现过一次的点。
考虑让叶子作为环的代表点。我们寻找到了一些性质：由于树高 \(<\frac{n}{k}\)，故而树至少有 \(k\) 个叶子，同时根据题目给出的“每个叶子度数 \(\geq3\)”，易得出：每个叶子至少有两条返祖边（无向图的 \(\text{DFS}\) 树没有横叉边）。
此时，再尝试分析叶子 \(i\) 两条返祖边 \((i,p1),(i,p2)\) 能构成的方案（假设 \(p1\) 的深度 \(<p1\) 的深度）。那么环的情况必定是以下三种之一：
分类讨论一下即可发现，三种情况中必定有一种环长不为 \(3\) 的倍数。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 2.5e5 + 10;
int n, m, k, tot; vector<int> e[N];
int fa[N], p1[N], p2[N], vis[N], dfn[N], dep[N];
void jump(int u, int p, int c = 0){
printf("%d\n", dep[u] - dep[p] + 1 + (c > 0));
if(c) printf("%d ", c);
for(int i = u; i != fa[p]; i = fa[i]) printf("%d ", i);
}
void dfs(int u){
dfn[u] = ++tot, dep[u] = dep[fa[u]] + 1;
for(int &v: e[u]) if(v != fa[u]){
if(!dfn[v]) vis[fa[v] = u] = 1, dfs(v);
else p2[u] = (p1[u]? v : 0), p1[u] = (p1[u]? p1[u] : v);
}
}
int main(){
scanf("%d%d%d", &n, &m, &k);
FL(i, 1, m){
int u, v; scanf("%d%d", &u, &v);
e[u].emplace_back(v), e[v].emplace_back(u);
}
dfs(1);
FL(i, 1, n) if(dep[i] > (n - 1) / k){
printf("PATH\n"), jump(i, 1);
printf("\n"); return 0;
}
printf("CYCLES\n");
FL(i, 1, n) if(!vis[i] && k-- > 0){
if((dep[i] - dep[p1[i]]) % 3 < 2) jump(i, p1[i]);
else if((dep[i] - dep[p2[i]]) % 3 < 2) jump(i, p2[i]);
else{
if(dep[p1[i]] > dep[p2[i]]) swap(p1[i], p2[i]);
jump(p2[i], p1[i], i);
}
putchar('\n');
}
return 0;
}