强烈推荐此题。图论和DP结合。
首先，我们分析一下分组的要求：
1、把所有的人分成2组，每组至少有1人；
2、每组之间的人两两认识。
非常明显，如果存在两个人A和B，A不认识B，或B不认识A，那么A和B一定不能分在同一组。因此，我们以人为结点重新构造一个图G。假如A和B不能分在同一组，那么就在G中增加一条无向边(A,B)。这样，我们就得到了一个较为“单纯”的模型。下面我们对这个模型进行简单分析。
我们先研究G的一个连通分量K1。对于这个连通分量，可以先求出K1的生成树T1。对于K1中的任意结点a，假如a在T1中的深度为奇数，我们就把a加入点集S1；否则我们把a加入点集S2（S1,S2最初为空集）。显然最后S1,S2的交集为空。
不难证明，如果存在不同结点p和q，p和q同属于S1或S2，而且G中存在边(p,q)，那么要做到满足题目要求的分组是不可能的，应输出No solution。否则，我们就得到了连通分量K1的唯一分组方案：分为S1,S2两组。
对于G中的每个连通分量Ki，我们可以求出相应的S1i,S2i。最后，我们的目的是把全部人分为2组。也就是说，对于i=1,2,3,...,m，我们必须决定把S1i中的人分到第1组，S2i中的人分到第2组，还是做刚好相反的处理。由于题目要求最后两组的总人数差最小，我们可以用动态规划的办法来确定究竟选取上面的哪种决策。
不妨假设G中共有m个连通分量，记|S1i|=xi,|S2i|=yi(i=1,2,3,...,m)。若xi < yi，我们就交换xi和yi（这样不影响结果的正确性）。记wi = xi - yi。那么只要对所有的wi做“半个背包”即可。也就是说，凑出尽量接近sum(wi)的数。接下去就非常简单了。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-29 12:07:38
File Name: pku1112.cpp
Description:
************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 110;
int n;
int g[maxn][maxn];
int cnt_id;
int id[maxn];
int w[maxn];
void dfs(int now, int new_id)
{
id[now] = new_id;
for (int i = 1; i <= n; i++) if (id[i] == 0 && g[now][i])
dfs(i, new_id);
}
void make_id()
{
cnt_id = 0;
memset(id, 0, sizeof(id));
for (int i = 1; i <= n; i++) if (id[i] == 0)
dfs(i, ++cnt_id);
}
int set_mask[maxn];
void divide(int cid, int now, int set_id, int *set_mask)
{
*(set_mask + now) = set_id;
for (int i = 1; i <= n; i++) if (*(set_mask + i) == 0 && id[i] == cid && g[now][i])
divide(cid, i, 3 - set_id, set_mask);
}
int ok()
{
memset(set_mask, 0, sizeof(set_mask));
for (int i = 1; i <= cnt_id; i++)
{
for (int j = 1; j <= n; j++)
if (id[j] == i)
{
divide(i, j, 1, set_mask);
break;
}
int cntx = 0;
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
cntx++;
int cnty = 0;
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
cnty++;
if (cntx < cnty)
{
for (int j = 1; j <= n; j++) if (id[j] == i)
set_mask[j] = 3 - set_mask[j];
}
w[i] = abs(cntx - cnty);
int flag = 1;
for (int j = 1; j <= n && flag; j++) if (id[j] == i && set_mask[j] == 1)
for (int k = 1; k <= n && flag; k++) if (id[k] == i && set_mask[k] == 1 && j != k)
if (g[j][k]) flag = 0;
for (int j = 1; j <= n && flag; j++) if (id[j] == i && set_mask[j] == 2)
for (int k = 1; k <= n && flag; k++) if (id[k] == i && set_mask[k] == 2 && j != k)
if (g[j][k]) flag = 0;
if (flag == 0) return 0;
}
return 1;
}
typedef struct ptr_t
{
int ptr, value;
};
ptr_t pre[maxn];
int mask[maxn];
void print(int now)
{
if (pre[now].value == 0)
return;
print(pre[now].ptr);
mask[pre[now].value] = 1;
}
void dp()
{
int f[maxn];
memset(f, 0, sizeof(f));
memset(pre, 0, sizeof(pre));
f[0] = 1;
int sum = 0;
for (int i = 1; i <= cnt_id; i++) sum += w[i];
for (int i = 0; i <= cnt_id; i++)
for (int j = sum / 2; j >= 0; j--) if (f[j] && !f[j + w[i]])
{
f[j + w[i]] = 1;
pre[j + w[i]].ptr = j;
pre[j + w[i]].value = i;
}
int ans_i;
for (int i = sum / 2; i >= 0; i--) if (f[i])
{
ans_i = i;
break;
}
memset(mask, 0, sizeof(mask));
print(ans_i);
int cnt1 = 0;
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
cnt1++;
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
cnt1++;
}
}
printf("%d", cnt1);
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
printf(" %d", j);
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
printf(" %d", j);
}
}
printf("\n");
int cnt2 = 0;
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
cnt2++;
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
cnt2++;
}
}
printf("%d", cnt2);
for (int i = 1; i <= cnt_id; i++)
{
if (mask[i])
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 2)
printf(" %d", j);
}
else
{
for (int j = 1; j <= n; j++) if (id[j] == i && set_mask[j] == 1)
printf(" %d", j);
}
}
printf("\n");
}
int main()
{
int tmp[maxn][maxn];
while (scanf("%d", &n) != EOF)
{
memset(tmp, 0, sizeof(tmp));
for (int i = 1; i <= n; i++)
{
int t;
while (scanf("%d", &t), t != 0)
tmp[i][t] = 1;
}
memset(g, 0, sizeof(g));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && (tmp[i][j] == 0 || tmp[j][i] == 0))
g[i][j] = g[j][i] = 1;
make_id();
int t = ok();
if (!t)
printf("No solution\n");
else
dp();
}
return 0;
}