大型补档计划
看到分成两组，想到二分图判定 + 染色。
二分图的特点是两个有矛盾的点连一条边，考虑在这道题中，如果 \(a, b\) 中有一个人不认识对方（或者两个人互不认识），就不可能分在一组，可以在 \((a, b)\) 连一条无向边。
但是由于图不连通，每个联通块染色跑出两种颜色的数量 \(c_1, c_2\) 后（跑不出来无解），让两队数量接近，等价于让一队的数量 $ <= \frac{N}{2}$ 且最大，我们可以把这两个当做一组，把 \(cnt\) 个联通块当做物品，做分组背包选出一队的人员（并且强制选择），因为答案输出任意一组方案，倒序递推出答案即可。
切忌强制转移！因为不强制转移可能出现一组都不选，而题目要求每个队员必须在一队（会 WA 53）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 105;
int n, c1, c2, cnt, col[N], vis[N];
int f[N][N], a[N][N], b[N][N], d[N];
vector<int> ans[2];
bool g[N][N];
bool dfs(int u, int t, int c) {
col[u] = c, vis[u] = t;
c == 1 ? c1++ : c2++;
for (int v = 1; v <= n; v++) {
if (v != u && (!g[u][v] || !g[v][u])) {
if (!col[v]) {
if (!dfs(v, t, 3 - c)) return false;
} else if(col[v] == c) return false;
}
}
return true;
}
void work(int i, int j) {
if (i == 0) return;
if (b[i][j]) d[i] = b[i][j];
work(i - 1, a[i][j]);
}
int main() {
memset(f, 0xcf, sizeof f);
f[0][0] = 0;
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) {
while (scanf("%d", &x), x) {
g[i][x] = true;
}
}
int V = n >> 1;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
c1 = 0, c2 = 0;
if(!dfs(i, ++cnt, 1)) {
puts("No solution");
return 0;
}
for (int j = V; j >= 0; j--) {
if (j >= c1 && f[cnt - 1][j - c1] + c1 >= f[cnt][j]) {
f[cnt][j] = f[cnt - 1][j - c1] + c1;
a[cnt][j] = j - c1, b[cnt][j] = 1;
}
if (j >= c2 && f[cnt - 1][j - c2] + c2 >= f[cnt][j]) {
f[cnt][j] = f[cnt - 1][j - c2] + c2;
a[cnt][j] = j - c2, b[cnt][j] = 2;
}
}
}
}
int res = 0, t = -1;
for (int i = 0; i <= V; i++)
if (f[cnt][i] > res) res = f[cnt][i], t = i;
work(cnt, t);
for (int i = 1; i <= n; i++) {
if ((col[i] == 1 && d[vis[i]] == 1) || (col[i] == 2 && d[vis[i]] == 2)) ans[0].push_back(i);
else ans[1].push_back(i);
}
for (int i = 0; i < 2; i++) {
printf("%d ", ans[i].size());
for (int j = 0; j < ans[i].size(); j++) printf("%d ", ans[i][j]);
puts("");
}
return 0;
}