大意: 无向图, 无重边自环, 每个点度数 >=3, 要求完成下面任意一个任务
找一条结点数不少于 n/k 的简单路径
找 k 个简单环, 每个环结点数小于 n/k, 且不为 3 的倍数, 且每个环有一个特殊点 $x$, $x$ 只属于这一个环
任选一棵生成树, 若高度 >=n/k, 直接完成任务 1, 否则对于叶子数一定不少于 k, 而叶子反向边数 >=2, 一定可以构造出一个环
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <math.h>
- #include <set>
- #include <map>
- #include <queue>
- #include <string>
- #include <string.h>
- #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<int,int> 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;}
- //head
- const int N = 1e6+10;
- int n, m, k;
- vector<int> 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]<dep[y]) swap(x,y);
- printf("%d\n", dep[x]-dep[y]+2);
- for (; printf("%d",x), x!=y; x=fa[x]) ;
- printf("%d", z);
- }
- puts("");
- }
- }
来源: http://www.bubuko.com/infodetail-2981310.html