题解 P7320【可怜的团主】

_zy_ · 2021-08-24 09:56:03 · 题解

题目传送门

题目大意：

给定一张简单无向连通图。

问是否能找到 \lceil \frac{n}{6}\rceil 条路径走完所有点，或大小为 \lfloor \frac{n}{3} \rfloor 个独立集并找到其中一个。

若没有则 Poor lnlhm

~~通过套取数据~~ 得出并不存在没有的情况（结尾给出证明）

考虑 dfs 树，将整张图 dfs 后，回溯时处理出独立集。

如果可以将 x 节点放入，就将其所联的点都标记为不可放入。

if(!ind[x])
{
    ans.push_back(x);
    for(int i=fir[x];i;i=nex[i])
        ind[poi[i]]=1;
    if(ans.size()==n/3) Print_2();
}

再处理后的一颗树上，存下叶子节点，将所有叶子进行匹配，如果不能进行完美的匹配，就可以把根节点1看做叶子节点。

将所有叶子节点按照 dfs 序排序，匹配时可以将 lef_i 和 lef_{i+\frac{num}{2}} 当做起点和终点，再用 dfs 树时处理的父亲节点一个一个向上跳就可以了。

处理后如果不能达到 \lceil \frac{n}{6}\rceil , 就补上单个点就好。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define N 1000010
using namespace std;
int re() {
    int p=0,f=1; char i=getchar();
    while(i<'0'||i>'9') {if(i=='-')  f=-1;i=getchar();}
    while(i>='0'&&i<='9')   p=p*10+i-'0',i=getchar();
    return f*p;
}
int n,m,sum,cnt,num,lit;
int fir[N],nex[N],poi[N];
int dfn[N],dep[N],f[N],loc[N];
bool ind[N];
int lef[N];
vector<int> ans;
void ins(int x,int y) {
    nex[++sum]=fir[x];
    poi[sum]=y;
    fir[x]=sum;
}
bool cmp(int x,int y) {
    return dfn[x]<dfn[y];
}
int a[N],b[N];
void Jump(int x,int y)
{
    lit++;
    int step_a=0,step_b=0;
    while(x!=y)
    {
        if(dep[x]>dep[y])
            a[++step_a]=x,x=f[x];
        else
            b[++step_b]=y,y=f[y];
    }
    a[++step_a]=x;
    printf("%d ",step_a+step_b);
    for(int i=1;i<=step_a;i++)
        printf("%d ",a[i]);
    for(int i=step_b;i>=1;i--)
        printf("%d ",b[i]);
}
void Print_1() {
    printf("1\n");
    for(int i=1;i<=num/2;i++)
    {
        int u=lef[i],v=lef[i+num/2];
        Jump(u,v);
        puts("");
    }
    int lim=n/6;
    if(n%6) lim++;
    for(int i=lit;i<lim;i++)
        printf("1 %d\n",i);
}
void Print_2() {
    printf("2\n");
    for(int i=0;i<ans.size();i++)
        printf("%d ",ans[i]);
    exit(0);
}
void dfs(int x,int fa)
{
    int flag=0;
    dfn[x]=++cnt;
    dep[x]=dep[fa]+1;
    loc[cnt]=x;
    f[x]=fa;
    for(int i=fir[x];i;i=nex[i]) {
        int p=poi[i];
        if(dep[p])  continue;
        dfs(p,x);
        flag++;
    }
    if(flag==0||(flag==1&&x==1))
        lef[++num]=x;
    if(!ind[x]) {
        ans.push_back(x);
        for(int i=fir[x];i;i=nex[i])
            ind[poi[i]]=1;
        if(ans.size()==n/3) Print_2();
    }
}
int main()
{
    n=re(); m=re();
    for(int i=1;i<=m;i++) {
        int u,v;
        u=re(); v=re();
        ins(u,v);
        ins(v,u);
    }
    dfs(1,0);
    sort(lef+1,lef+num+1,cmp);
    Print_1();
    return 0;
}

证明：

如果最大独立集小于 \lfloor \frac{n}{3} \rfloor ，将每两个独立集需要一条边，至多需要 \lceil \frac{n}{6} \rceil 边就可以使独立集联通，也即整张图联通。

如果 \lceil \frac{n}{6} \rceil 条边不能使图联通，那么同理，最大独立集一定大于 \lfloor \frac{n}{3} \rfloor 。

故不存在最大独立集既小于 \lfloor \frac{n}{3}\rfloor 时 \lceil \frac{n}{6} \rceil 条边不能使图联通。

如有不妥之处，请不要吝啬您的评论~

qwq