题意

求出一个大于 n \lceil\sqrt{n}\rceil n 的环或找出 n \lceil\sqrt{n}\rceil n 个点的独立集。

分析

d f s dfs dfs 树可以找最大环。
d f s dfs dfs 树是什么?就是从某个点进行 d f s dfs dfs 形成的树,如图。

深色的是树边,浅色的是非树边。

d f s dfs dfs 树有个性质:每条非树边 ( a , b ) (a, b) (a,b) 都连向子树中某个点。
那么, a a a b b b 在树上的链与非树边 ( a , b ) (a,b) (a,b) 会形成一个环,环的大小为 d e p [ a ] d e p [ b ] + 1 |dep[a]-dep[b]|+1 dep[a]dep[b]+1
容易看出,最大环一定由某条链和某条非树边组成。
所以我们可以用一个栈维护根到当前点的链,当环的大小超过 n \lceil\sqrt{n} \rceil n 时,就输出。

下面证明如果不存在这种环,就一定存在至少 n \lceil\sqrt{n} \rceil n 个点的独立集
由于不存在这种环,因此每个点最多有 n 2 \lceil\sqrt{n} \rceil -2 n 2 条非树边,也就是说,我们每选择一个点,最多会导致 n 1 \lceil\sqrt{n}\rceil -1 n 1 个点无法被选。所以最少可以选 n \lceil\sqrt{n} \rceil n 个点,按深度从大到小选即可。

代码如下

#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long LL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
struct node{
	int a, b, n;
}d[N * 2];
int h[N], fa[N], dep[N], tag[N], v[N * 2], cnt = 1, sq;
vector<int> vec, ans;
void cr(int a, int b){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
	int i, j, b;
	vec.push_back(a);
	for(i = h[a]; i; i = d[i].n){
		if(v[i]) continue;
		v[i] = v[i ^ 1] = 1;
		b = d[i].b;
		if(!dep[b]){
			dep[b] = dep[a] + 1;
			dfs(b);
		}
		else{
			if(dep[a] - dep[b] >= sq - 1){
				printf("2\n%d\n", dep[a] - dep[b] + 1);
				for(j = dep[b] - 1; j < dep[a]; j++){
					printf("%d ", vec[j]);
				}
				exit(0);
			}
		}
	}
	if(!tag[a]){
		tag[a] = 1;
		ans.push_back(a);
		for(i = h[a]; i; i = d[i].n){
			b = d[i].b;
			tag[b] = 1;
		}
	}
	vec.pop_back();
}
int main(){
	int i, j, n, m, a, b;
	scanf("%d%d", &n, &m);
	sq = sqrt(n - 1) + 1;
	for(i = 1; i <= m; i++){
		scanf("%d%d", &a, &b);
		cr(a, b);
		cr(b, a);
	}
	dep[1] = 1;
	dfs(1);
	printf("1\n");
	for(i = 0; i < sq; i++) printf("%d ", ans[i]);
	return 0;
}