[D. Ehab's Last Corollary] dfs树

D. Ehab‘s Last Corollary dfs树

题目大意：
给你一个n个点m条边的图，让你找一个大小是k的独立子集或者一个长度为k的简单子环
题解：
很明显的一个dfs树的题目，也应该可以很快证明出这两个一定有一个成立。
假设最小的环长度是k+1，那么显而易见 (k+1)/2 一定有这么多个点互补连边
如果找到环长度小于等于k的，那么直接输出答案

题目难度不大，基本的dfs树的操作，和之前写的类似：

dfs树 E. Johnny Solving

F. Ehab‘s Last Theorem dfs树！！！

但是要注意的是要按照dep从大到小排序，因为dep越大则里这个点的距离越近，每次要找最近的点来判断才是正确的。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
/***
题目大意：
给你一个n个点m条边的图，让你找一个大小是k的独立子集或者一个长度为k的简单子环
题解：
很明显的一个dfs树的题目，也应该可以很快证明出这两个一定有一个成立。
假设最小的环长度是k+1，那么显而易见 (k+1)/2 一定有这么多个点互补连边
如果找到环长度小于等于k的，那么直接输出答案
***/

vector<int>G[maxn];
void add(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
int n,m,k,flag = 0;
int dep[maxn],fa[maxn],ver[maxn],tot,vis[maxn];
bool cmp(int i,int j){
	return dep[i]>dep[j];
}
void dfs(int u,int pre,int d){
	// printf("u=%d pre=%d d=%d\n", u,pre,d);
	ver[++tot] = u;
	dep[u] = d,fa[u] = pre;
	int len = G[u].size();
	sort(G[u].begin(),G[u].end(),cmp);
	for(int i=0;i<len;i++){
		int v = G[u][i];
		if(v == pre) continue;
		if(!dep[v]) dfs(v,u,d+1);
		else{
			if(flag) return ;
			int len = dep[u]-dep[v]+1;
			// printf("len=%d u=%d v=%d\n", len,u,v);
			flag = 1;
			if(len<=k){
				printf("2\n");
				printf("%d\n", len);
				int x = u;
				while(x!=v){
					printf("%d ", x);
					x = fa[x];
				}
				printf("%d\n", v);
			}
			else{
				printf("1\n");
				int x = fa[u];
				k = (k+1)/2;
				while(dep[x]>=dep[v]){
					k--;
					printf("%d%c", x,k?‘ ‘:‘\n‘);
					if(!k) break;
					x = fa[x],x = fa[x];
				}
			}
			return ;
		}
	}
}
int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs(1,0,1);
	if(!flag){
		printf("1\n");
		k = (k+1)/2;
		for(int i=n;i>=1;i--){
			int x = ver[i];
			if(vis[x]) continue;
			k--;
			printf("%d%c",x, k?‘ ‘:‘\n‘);
			if(!k) break;
			vis[x] = true;
			vis[fa[x]] = true;
		}
	}
	return 0;
}

[D. Ehab's Last Corollary] dfs树

原文：https://www.cnblogs.com/EchoZQN/p/13628416.html