CF1364D Ehab's Last Corollary 题解 (构造/独立集/找最小环)

作者：XiaoQuQu，发表于 Sat Jul 20 2024。

题意

给出一张 n 个点的无向连通图和一个常数 k。

你需要解决以下两个问题的任何一个：

1. 找出一个大小为 $\lceil \frac k2\rceil$ 的独立集。
2. 找出一个大小不超过 k 的环。

独立集是一个点的集合，满足其中任意两点之间在原图上没有边直接相连。

可以证明这两个问题必然有一个可以被解决。

题解

考虑如果没有环，可以对这棵树进行一个黑白染色，必定有一个颜色数量是大于等于 $\frac n2$ 的。

考虑如果有一个环，我们找到一个极小环（即这个环内部没有其它环），然后对这个环的环长进行一个分类讨论：

1. 环长 $l\le k$，我们已经找到了一个问题 2 的解。
2. 环长 $l>k$，对这个环进行一个黑白染色，发现必定有一个颜色数量大于等于 $\frac k2$，且由于这是一个极小环，可以保证黑白染色后是独立的，所以我们找到了一个问题 1 的解。

如何找极小环：在 DFS 的过程中对于第一个有返祖边的点 $u$，对于他的每个返祖边 $(u,v)$，我们取 $v$ 深度最大的那条边。这样 $(u,v)$ 覆盖的环一定是一个极小环。

证明：考虑反证法，设 $(u,v)$ 内部有一个极小环 $(x,y)$，分类讨论。如果 $u\ne y$，我们一定会在 $y$ 的时候就找到一个极小环。如果 $u=y$ 且 $x\ne v$，由我们的过程得 $dep_v>dep_x$，所以 $x$ 一定是 $v$ 的祖先，与 $(x,y)$ 是极小环矛盾。故 $(u,v)$ 是极小环。

const int MAXN = 1e5 + 5;
int n, m, k, dep[MAXN], st[MAXN], tp;
vector<int> G[MAXN];

void dfs(int x, int fat) {
	dep[x] = dep[fat] + 1;
	st[++tp] = x;
	int lws = 0; 
	for (auto u:G[x]) {
		if (u == fat) continue;
		if (dep[u] && dep[u] < dep[x]) {
			if (!lws || dep[u] > dep[lws]) lws = u;
		}
	}
	if (lws) {
		int u = lws;
		int len = dep[x] - dep[u] + 1;
		if (len <= k) {
			cout << 2 << endl << len << endl;
			while (st[tp] != u) {
				cout << st[tp] << ' ';
				tp--;
			}
			cout << u << endl;
		} else {
			int c = 0, cnt = 0;
			cout << 1 << endl;
			while (cnt < ceil(k * 1.0 / 2)) {
				if (!c) {
					c = 1;
				} else {
					cnt++;
					cout << st[tp] << ' ';
					c = 0;
				}
				tp--;
			}
		}
		exit(0);
	}
	for (auto u:G[x]) {
		if (u == fat) continue;
		if (!dep[u]) dfs(u, x);
	}
	tp--;
}

int col[MAXN], tcnt[2];

void dfs2(int x, int fat) {
	col[x] = 1 ^ col[fat];
	tcnt[col[x]]++;
	for (auto u:G[x]) {
		if (u == fat) continue;
		dfs2(u, x);
	}
}

void work() {
	cin >> n >> m >> k;
	for (int i = 1, u, v; i <= m; ++i) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0);
	dfs2(1, 0);
	cout << 1 << endl;
	int cnt = 0;
	int tt = tcnt[1] > tcnt[0];
	for (int i = 1; i <= n; ++i) {
		if (col[i] == tt) {
			cout << i << ' ';
			++cnt;
		}
		if (cnt == ceil(k * 1.0 / 2)) return;
	}
}