题目如上。

本关卡需要先了解：染色+背包

分析：
我们先不考虑让两个队伍规模尽量平均，先满足两个队伍中两两互相认识的条件。

题目给出的是A认识B（B不一定认识A），可是A认识B的话，不一定说明A和B就在一个队伍里，这样的一条关系显得没有什么用。

所以，我们知道所有的认识关系，自然能知道谁不认识谁，如果A不认识B，那么一定满足A和B不在一支队伍内，这样就把条件变得有用了。

我们以不认识的关系作为一张新图（就是补图啦），进行染色（就两种颜色），若染色不成功就“No solution”。

要注意这张新图可能是不联通的，于是，在同一联通块内同一颜色的只能是一个队伍的。

接下来就要考虑让两个队伍规模尽量平均的条件：

设两支队伍分别叫T1，T2。（Team1,Team2）

我们要统计每个联通块内两种颜色各有几个点，每个联通块统计出两个数字，T1选一个数，于是T2选另一个数。

每个联通块怎么选是互不影响的，因为联通块间没有连边，代表一个联通块中任何一个点都与除它以外所有联通块中的任何一个点认识，所以两个数选哪个都没关系。

于是就相当于T1,T2在每个联通块的两个数中选数，选出来的数的和，也就是队伍人数，要尽量接近。

大家可能想到了，用背包就好了嘛。

①可以用f[i][j]表示一支队伍选了第1~i的联通块的和能否为j，最后找最接近总人数/2的j，也就是n/2。

代码①（写了循环队列）：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n;
bool map[110][110];
int color[110];
int bl[110],cnt;
bool dfs(int x)
{
    bl[x]=cnt;
    for(int y=1;y<=n;y++)if(map[x][y]||map[y][x])
    {
        if(color[y]==-1)
        {
            color[y]=1-color[x];
            if(!dfs(y))return false;
        }
        else if(color[y]==color[x])return false;
    }
    return true;
}
int a[110][2],pr[110][110],who[110][110];bool f[2][110];
int ans[110],anslen;
int main()
{
    n=ri();
    memset(map,true,sizeof(map));
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            int y=ri();
            if(y==0)break;
            map[i][y]=false;
        }
        map[i][i]=false;
    }
    memset(color,-1,sizeof(color));cnt=0;
    for(int i=1;i<=n;i++)if(color[i]==-1)
    {
        color[i]=0;cnt++;
        if(!dfs(i)){puts("No solution");return 0;}
    }
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)a[bl[i]][color[i]]++;
    memset(f[0],false,sizeof(f[0]));f[0][0]=true;
    for(int i=1;i<=cnt;i++)
    {
        int w=(i&1);
        memset(f[w],false,sizeof(f[w]));
        for(int j=n;j>=0;j--)if(f[1-w][j])
        {
            int cc=j+a[i][0];
            if(cc<=n)
            {
                f[w][cc]=true;
                pr[i][cc]=j;
                who[i][cc]=0;
            }
            cc=j+a[i][1];
            if(cc<=n)
            {
                f[w][cc]=true;
                pr[i][cc]=j;
                who[i][cc]=1;
            }
        }
    }
    int l=n/2,r=((n&1)?(n/2+1):(n/2)),w=(cnt&1);
    while(l)
    {
        if(f[w][l]||f[w][r])break;
        l--;r++;
    }
    if(f[w][r])l=r;
    printf("%d",l);
    int nowi=cnt,nowj=l;
    anslen=0;
    while(nowi)
    {
        for(int j=1;j<=n;j++)if(bl[j]==nowi&&color[j]==who[nowi][nowj])ans[++anslen]=j;
        nowj=pr[nowi--][nowj];
    }
    sort(ans+1,ans+anslen+1);
    for(int i=1;i<=anslen;i++)printf(" %d",ans[i]);
    printf("\n%d",n-l);
    l=1;
    for(int i=1;i<=n;i++)
    {
        if(i!=ans[l])printf(" %d",i);
        else l++;
    }
    puts("");
    return 0;
}

②可以对每个联通酷块的两个数作差，f[i][j]表示第1~i的联通块作的差的和为j。

假设第一个数和第二个数的差为x，加上x表示T1选了第一个数，减去x表示T1选了第二个数。

最后找和最接近0的。

代码②(写了循环队列，注意j可能为负数，要把下标整体+n)：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n;
bool map[110][110];
int color[110];
int bl[110],cnt;
bool dfs(int x)
{
    bl[x]=cnt;
    for(int y=1;y<=n;y++)if(map[x][y]||map[y][x])
    {
        if(color[y]==-1)
        {
            color[y]=1-color[x];
            if(!dfs(y))return false;
        }
        else if(color[y]==color[x])return false;
    }
    return true;
}
int a[110][2],pr[110][210],who[110][210];bool f[2][210];
int ans[110],anslen;
int main()
{
    n=ri();
    memset(map,true,sizeof(map));
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            int y=ri();
            if(y==0)break;
            map[i][y]=false;
        }
        map[i][i]=false;
    }
    memset(color,-1,sizeof(color));cnt=0;
    for(int i=1;i<=n;i++)if(color[i]==-1)
    {
        color[i]=0;cnt++;
        if(!dfs(i)){puts("No solution");return 0;}
    }
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)a[bl[i]][color[i]]++;
    memset(f[0],false,sizeof(f[0]));f[0][n]=true;
    for(int i=1;i<=cnt;i++)
    {
        int cc=a[i][0]-a[i][1],w=(i&1);
        memset(f[w],false,sizeof(f[w]));
        for(int j=-n;j<=n;j++)if(f[1-w][j+n])
        {
            if(j+cc<=n&&j+cc>=-n)
            {
                f[w][j+cc+n]=true;
                pr[i][j+cc+n]=j+n;
                who[i][j+cc+n]=0;
            }
            if(j-cc<=n&&j-cc>=-n)
            {
                f[w][j-cc+n]=true;
                pr[i][j-cc+n]=j+n;
                who[i][j-cc+n]=1;
            }
        }
    }
    int l=0,w=(cnt&1);
    while(l<=n)
    {
        if(f[w][n+l]||f[w][n-l])break;
        l++;
    }
    if(f[w][n+l])printf("%d",(l+n)/2),l=n+l;//a-b=l,a+b=n
    else printf("%d",(n-l)/2),l=n-l;//a-b=-l,a+b=n
    int nowi=cnt,nowj=l;
    anslen=0;
    while(nowi)
    {
        for(int j=1;j<=n;j++)if(bl[j]==nowi&&color[j]==who[nowi][nowj])ans[++anslen]=j;
        nowj=pr[nowi--][nowj];
    }
    sort(ans+1,ans+anslen+1);
    for(int i=1;i<=anslen;i++)printf(" %d",ans[i]);
    printf("\n%d",n-anslen);
    l=1;ans[anslen+1]=0;
    for(int i=1;i<=n;i++)
    {
        if(i!=ans[l])printf(" %d",i);
        else l++;
    }
    puts("");
    return 0;
}