这不就是和圆桌骑士基本一样的思路吗。

因为很难直接处理相互认识的人（for循环+判断是否能拆成两个完全图且有一个完全图的大小为i？？？），所以我们把不互相认识的人连一条边（如果只有一个人认识对方，那么也不能在同一个团队）。

然后就会出现很多个联通块，对于每一个联通块二分图染色，如果满足条件的话就用背包求一下。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const int N = 110, M = 10010;

int n, t, color[N], fa[N], f[N][N]; bool bk[N];
int tot, Head[N], ver[M << 1], Next[M << 1];
int cnt, new_id[N], siz, ans[N];
vector<int> a[N][3];

void add(int x, int y) {
    tot++;
    ver[tot] = y;
    Next[tot] = Head[x];
    Head[x] = tot;
}

int findfa(int x) { return x == fa[x] ? x : fa[x] = findfa(fa[x]); }

bool dfs(int x, int now) {
    color[x] = now;
    a[new_id[x]][now].push_back(x);
    for (int i = Head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!color[y]) {
            if (!dfs(y, 3 - now)) return 0;
        }
        else if (color[x] == color[y]) return 0;
    }
    return 1;
}

void solve(int i, int j) {
    if (!i) return;
    for (int k = 0; k < a[i][f[i][j]].size(); k++)
        ans[++siz] = a[i][f[i][j]][k], bk[ans[siz]] = 1;
    solve(i - 1, j - a[i][f[i][j]].size());
}

int main() {
    cin >> n;
    tot = 1;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= n; i++) {
        memset(bk, 0, sizeof(bk));
        int x;
        while (~scanf("%d", &x) && x) bk[x] = 1;
        for (int j = 1; j <= n; j++)
            if (j != i && !bk[j]) add(i, j), add(j, i), fa[findfa(i)] = findfa(j);
    }
    for (int i = 1; i <= n; i++) 
        if (!new_id[findfa(i)]) new_id[i] = new_id[fa[i]] = ++cnt;
        else new_id[i] = new_id[fa[i]];
    for (int i = 1; i <= n; i++)
        if (!color[i] && !dfs(i, 1)) {
            puts("No solution");
            return 0;
        }
    t = n / 2;
    memset(f, -1, sizeof(f)); f[0][0] = 0;
    for (int i = 1; i <= cnt; i++) {
        int p1 = a[i][1].size();
        int p2 = a[i][2].size();
        for (int j = 0; j <= t; j++) {
            if (j >= p1 && f[i - 1][j - p1] != -1) f[i][j] = 1;
            if (j >= p2 && f[i - 1][j - p2] != -1) f[i][j] = 2;
        }
    }
    memset(bk, 0, sizeof(bk));
    for (int i = t; i >= 0; i--)
        if (f[cnt][i] != -1) {
            solve(cnt, i);
            break;
        }
    printf("%d ", siz);
    sort(ans + 1, ans + siz + 1);
    for (int i = 1; i <= siz; i++) printf("%d ", ans[i]);
    puts("");
    printf("%d ", n - siz);
    for (int i = 1; i <= n; i++) if (!bk[i]) printf("%d ", i);
    puts("");
    return 0;
}