本文共 1806 字，大约阅读时间需要 6 分钟。
大意: 无向图, 无重边自环, 每个点度数>=3, 要求完成下面任意一个任务
任选一棵生成树, 若高度>=n/k, 直接完成任务1, 否则对于叶子数一定不少于k, 而叶子反向边数>=2, 一定可以构造出一个环
#include #include #include #include #include #include #include #include #include #define REP(i,a,n) for(int i=a;i<=n;++i)#define PER(i,a,n) for(int i=n;i>=a;--i)#define hr putchar(10)#define pb push_back#define lc (o<<1)#define rc (lc|1)#define mid ((l+r)>>1)#define ls lc,l,mid#define rs rc,mid+1,r#define x first#define y second#define io std::ios::sync_with_stdio(false)#define endl '\n'using namespace std;typedef long long ll;typedef pair pii;const int P = 1e9+7, INF = 0x3f3f3f3f;ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}//headconst int N = 1e6+10;int n, m, k;vector g[N];int q[N];int dep[N], vis[N], fa[N];void dfs(int x, int f, int d) { vis[x]=1,fa[x]=f,dep[x]=d; if (d>=(n+k-1)/k) { puts("PATH"); printf("%d\n", d); while (x) printf("%d ",x),x=fa[x]; puts(""),exit(0); } int ok = 0; for (int y:g[x]) if (!vis[y]) { ok = 1, dfs(y,x,d+1); } if (!ok) q[++*q]=x;}int main() { scanf("%d%d%d", &n, &m, &k); REP(i,1,m) { int u, v; scanf("%d%d", &u, &v); g[u].pb(v),g[v].pb(u); } dfs(1,0,1); puts("CYCLES"); REP(i,1,k) { int x=0, y=0, z=q[i]; for (int t:g[z]) if (t!=fa[z]) { if (!x) x=t; else y=t; } if ((dep[z]-dep[x]+1)%3) { printf("%d\n",dep[z]-dep[x]+1); for (; printf("%d ",z), z!=x; z=fa[z]) ; } else if ((dep[z]-dep[y]+1)%3) { printf("%d\n",dep[z]-dep[y]+1); for (; printf("%d ",z), z!=y; z=fa[z]) ; } else { if (dep[x]
转载于:https://www.cnblogs.com/uid001/p/10500245.html