题意
给你一个 $|V| = n,|E|=m$, 无自环无重边的无向连通图，要求你从以下两种任务中选择一种完成：
- 找到一个 $=\lceil \sqrt{n} \rceil$ 的独立集
- 找到一个长度 $\geq \sqrt{n}$ 的简单环
$5 \leq n \leq 10^5,m \leq 2 \times 10^5$。
题解
发现自己好多基本事实都掌握的不好。。
结论 1：一定存在一个最长的简单环满足仅有一条非树边
证明
反证法。假设所有的最长简单环长度为 $mx$，都包含 $\geq 2$ 条非树边，首先无向图的非树边只有返祖边。我们从这个环上选取深度最浅和最深的两个点 $u,v$，发现一定有非树边 $(u,v)$。考虑取这条非树边和树上路径 $u \to v$ ，设这条环长度为 $len$，我们可以证明一定有 $len \geq mx$：因为每条非树边会让 $u \to v$ 方向走至少一步（深度至少加一）。
所以我们可以找到最长的简单环，如果 $\geq \sqrt{n}$ 输出就行了。如果所有都 $\leq \sqrt{n}$ 呢？
结论 2：最长的简单环长度 $\leq l$，那么一定满足所有点连出的非树边数量 $\leq l-2$。
证明
根据
$x+2 \leq l \Rightarrow x \leq l-2$
注意这里的正确性基于图去掉了所有重边的基础上。其实就是没影响
所以我们考虑每次找一个叶子：发现一定只有一条连向父亲的边和最多 $l-2$ 条非树边，也就是最多删去 $l-1$ 个点。直接每次找一个叶子，把它连向的点都删掉就好了。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2e5 + 5;
struct Edge{
int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;
int dep[MAXN];bool vis[MAXN];
int n,m;
inline void add(int u,int v){
e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}
int lim;
int fa[MAXN];
inline void dfs(int v,int fa=0){
vis[v] = 1;dep[v] = dep[fa]+1;::fa[v] = fa;
for(int i = head[v];i;i = e[i].nxt){
if(!vis[e[i].to]){
dfs(e[i].to,v);
}
else if(dep[e[i].to] > dep[v]){
if(dep[e[i].to]-dep[v]+1 >= lim){
int t = e[i].to;
printf("2\n%d\n",dep[e[i].to]-dep[v]+1);
while(t != ::fa[v]) printf("%d ",t),t = ::fa[t];
puts("");
exit(0);
}
}
}
}
int id[MAXN];
inline bool cmp(int x,int y){
return dep[x] > dep[y];
}
int tag[MAXN];
int main(){
scanf("%d%d",&n,&m);
lim = std::ceil(std::sqrt(1.0*n));
FOR(i,1,m){
int u,v;scanf("%d%d",&u,&v);
add(u,v);
}
dfs(1);
FOR(i,1,n) id[i] = i;
std::sort(id+1,id+n+1,cmp);
FOR(v,1,n){
if(tag[id[v]] == 2) continue;
tag[id[v]] = 1;
for(int i = head[id[v]];i;i = e[i].nxt) tag[e[i].to] = 2;
}
std::vector<int> ans;FOR(i,1,n) if(tag[i] == 1) ans.pb(i);
printf("%d\n",1);
FOR(i,1,lim) printf("%d ",ans[i-1]);puts("");
return 0;
}