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

题意

给出一张 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;
	}
}