Codeforces Round #628 (Div. 2) 一道比较简单的 搜索 题。

题目链接：Codeforces 1325F。

[toc]

系列题解：
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd；
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy；
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs；
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist；
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem；
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。

题目

原题

题意简述

给出一个 $n$ 个点 $m$ 条边的图，给你两个任务：

1. 找一个有且只有 $\left\lceil\sqrt{n}\right\rceil$ 个点的独立集；
2. 找一个至少有 $\left\lceil\sqrt{n}\right\rceil$ 个点的简单环；

任选一个完成。

数据范围

$$5\leq n\leq 10^5$$

$$n-1\leq m\leq 2\times 10^5$$

时空限制

见原题 pdf 文件。

题解

思路

考虑这样的做法，在图上 DFS，如果找到符合条件的环，则选择任务 $2$，然后输出，结束程序。

否则根据得到的信息找到满足条件的独立集即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100000+5;
const int MAXM=200000+5;

int n,m;
int cnt,head[MAXN],to[MAXM<<1],Next[MAXM<<1];
int fa[MAXN],dep[MAXN];

inline void Add_Edge(reg int u,reg int v){
    Next[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
    return;
}

int tot;
int Q[MAXN];
bool vis[MAXN];

inline void DFS(reg int ID){
    Q[++tot]=ID;
    dep[ID]=dep[fa[ID]]+1;
    for(reg int i=head[ID];i;i=Next[i])
        if(!dep[to[i]]){
            fa[to[i]]=ID;
            DFS(to[i]);
        }
        else if(dep[to[i]]<dep[ID]){
            reg int l=dep[ID]-dep[to[i]]+1;
            if(l*l>=n){
                printf("2\n%d\n",l);
                for(reg int j=ID;j;j=fa[j]){
                    printf("%d%c",j,j==to[i]?'\n':' ');
                    if(j==to[i])
                        break;
                }
                exit(0);
            }
        }
    return;
}

int main(void){
    n=read(),m=read();
    for(reg int i=1;i<=m;++i){
        static int u,v;
        u=read(),v=read();
        Add_Edge(u,v);
        Add_Edge(v,u);
    }
    DFS(1);
    reg int l=1;
    for(;l*l<n;++l);
    reg int rem=l;
    puts("1");
    for(reg int i=n;i>=1;--i){
        reg int x=Q[i];
        if(vis[x])
            continue;
        --rem;
        printf("%d%c",x,rem?' ':'\n');
        if(!rem)
            exit(0);
        for(reg int j=0;j<=l-2;++j){
            vis[x]=true;
            x=fa[x];
        }
    }
    return 0;
}