CF1103C

Aryper · 2021-10-01 23:24:10 · 个人记录

Johnny Solving

常用的技巧，图上不好做，就在图的生成树上做。

如果说生成树中有一条到根的路径 \ge \dfrac{n}{k} 说明结束了。

反之，则必然有 \ge k 个不同的叶子结点，我们取 k 个分别构造环。

题目条件显然，每个点的度数至少为 3，则对于每个叶子结点，都有至少 2 条返祖边。假设一条返到节点 x，一条返到节点 y，且 dt_x>dt_y。

那么因为没有重边的原因，构造一个 x\rightarrow p \rightarrow x 的环的长度至少为 3；同样因为没有重边的原因，构造 y\rightarrow p\rightarrow y 的环的长度就一定大于 3。

那么如果以上两个环中的一个环，满足了长度大于 3 且不为 3 的倍数的条件，我们就可以直接输出了。反之，我们可以构造一个 p\rightarrow x\rightarrow y \rightarrow p 的环，因为根据证明，上面两个环不满足的肯定是不为 3 的倍数的条件，那么我们就可以得到：

2 式减 1 式可得 dt_x-dt_y\equiv 0\pmod 3

那么针对 p\rightarrow x\rightarrow y \rightarrow p 这个环，我们发现它的长度为 dt_x-dt_y+2，那么板上钉钉的就会有 dt_x-dt_y+2\equiv 2\pmod 3，我们找到了满足条件的环，输出即可。

于是就做完了。

相当考验逻辑思维和构造能力的一道好题。

代码略长，不要彷徨。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=2.5e5,M=5e5;

ll n,m,flg,k,u,v,tot,cnt;

ll ver[M*2+5],nxt[M*2+5],head[N+5],dt[N+5],fa[N+5],lf[N+5];

bool vis[N+5];

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

void dfs(ll p,ll fath) {
    dt[p]=dt[fath]+1;vis[p]=1;fa[p]=fath;
//  printf("dt[%lld]=%lld\n",p,dt[p]);
    if(dt[p]>=(n+k-1)/k) {
        flg=1;
        printf("PATH\n");
        writeln(dt[p]);
        write(p);putchar(' ');
        return;
    }
    ll tmp_is_lf=1;
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fath||vis[ver[i]]) continue;
        tmp_is_lf=0;
        dfs(ver[i],p);
        if(flg) {
            write(p);putchar(' ');return;
        }
    }
    if(tmp_is_lf) {
        lf[++cnt]=p;
    }
}

void _dfs(ll p,ll target) {
    write(p);putchar(' ');
    if(p==target||p==0) return;
    _dfs(fa[p],target);
}

int main() {

    n=read();m=read();k=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();
        add(u,v);add(v,u);
    }

    dfs(1,0);

    if(!flg) {
        printf("CYCLES\n");
        for(ll i=1;i<=k;i++) {
            ll p=lf[i],x=0,y=0,len=0;
            for(ll j=head[p];j;j=nxt[j]) {
                if(ver[j]==fa[p]) continue;
                if(!x) {x=ver[j];continue;}
                if(!y) {y=ver[j];break;}
            }
            if(dt[x]<dt[y]) swap(x,y);
            if((dt[p]-dt[x]+1)%3!=0) {
                len=dt[p]-dt[x]+1;writeln(len);
                _dfs(p,x);
            }
            else
            if((dt[p]-dt[y]+1)%3!=0) {
                len=dt[p]-dt[y]+1;writeln(len);
                _dfs(p,y);
            }
            else {
                len=dt[x]-dt[y]+2;writeln(len);
                write(p);putchar(' ');
                _dfs(x,y);
            }
            putchar('\n');
        }
    }

    return 0;
}