二分图45pts求助

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }

    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n;
int g[105][105];

int cnt;
int head[105][2],pre[105],to[105];

void link(int x,int col,int y)
{
    to[++cnt]=y;
    pre[cnt]=head[x][col];
    head[x][col]=cnt;
}

int tot;
int col[105],f[105][2];
void dfs(int x,int c)
{
    f[tot][c]++;
    col[x]=c;
    link(tot,c,x);
    for(int i=1;i<=n;i++)
    {
        if(i==x) continue;
        if(!g[x][i])
        {
            if(col[i]==c)
            {
                cout<<"No solution";
                exit(0);
            }
            if(col[i]==1-c) continue;
            dfs(i,1-c);
        }
    }
}

int ans;
int dp[105][105],path[105][105];
void solve()
{
    dp[0][0]=1;
    for(int i=1;i<=tot;i++)
    {
        for(int j=0;j<=n/2;j++)
        {
            if(j>=f[i][0]) dp[i][j]|=dp[i-1][j-f[i][0]],path[i][j]=0;
            if(j>=f[i][1]) dp[i][j]|=dp[i-1][j-f[i][1]],path[i][j]=1;
//          cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }

    for(int i=n/2;i>=0;i--)
    {
        if(dp[tot][i])
        {
            ans=i;
            break;
        }
    }
}

bool flag[105];
void print()
{
    int tmp=ans,sum=0;
    for(int i=cnt;i;i--)
    {
        for(int j=head[i][path[i][tmp]];j;j=pre[j])
        {
            int t=to[j];
            sum++;
            flag[t]=1;
        }
        tmp-=f[i][path[i][tmp]];
    }

    cout<<sum<<" ";
    for(int i=1;i<=n;i++)
    {
        if(flag[i]) cout<<i<<" ";
    }
    cout<<endl<<n-sum<<" ";
    for(int i=1;i<=n;i++)
    {
        if(!flag[i]) cout<<i<<" ";
    }

}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int k;
        k=read();
        while(k!=0) g[i][k]=1,k=read();
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(g[i][j]!=g[j][i]) g[i][j]=g[j][i]=0;
        }
    }

    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++)
    {
        if(col[i]==-1)
        {
            tot++;
            dfs(i,1);
        }
    }

    solve();
    print();

    return 0;
}

/*
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0
*/