[AtCoder] [經典競程 90 題] 026 - Independent Set on a Tree（★4）

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_z
題目大意:
給一棵$n$個點的樹，要你找出$\frac{n}{2}$個彼此不相鄰的點。

---

隨意找個點當根，接著每個點按深度奇偶性分組，分成兩組後根據鴿籠原理(?)，一定有一組大小至少$\frac{n}{2}$，那他就可以是答案了。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

vector<int> G[N];

int c[N];
void dfs(int u, int f) {
	for (int v: G[u]) {
		if (v == f) continue;
		c[v] = c[u] ^ 1;
		dfs(v, u);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 1);
	vector<int> s[2];
	for (int i = 1; i <= n; ++i)
		s[c[i]].push_back(i);
	if (s[0].size() < s[1].size()) {
		swap(s[0], s[1]);
	}
	for (int i = 0; i < n / 2; ++i)
		cout << s[0][i] << " \n"[i == n / 2 - 1];
	return 0;
}