CF1325F Ehab's Last Theorem（dfs树

题意

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

分析

用 $dfs$dfs 树可以找最大环。
$dfs$dfs 树是什么？就是从某个点进行 $dfs$dfs 形成的树，如图。

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

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

下面证明如果不存在这种环，就一定存在至少 $\lceil \sqrt{n}\rceil$⌈n ​⌉个点的独立集
由于不存在这种环，因此每个点最多有 $\lceil \sqrt{n}\rceil -2$⌈n ​⌉−2 条非树边，也就是说，我们每选择一个点，最多会导致 $\lceil \sqrt{n}\rceil -1$⌈n ​⌉−1 个点无法被选。所以最少可以选 $\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;
}