萌新91pts求调

思路和题解一样，我这里存快的方法比较特别，希望 dalao 能够通过代码理解 QAQ.

#include<iostream>
using namespace std;
const int MAXN=105;
int n,u;
bool knw[MAXN][MAXN];
bool con[MAXN][MAXN];
int col[MAXN];//col[i] 对立面 col[i]^1.
int sum[MAXN];
bool vis[MAXN];//i子阵是否在 A 中 
bool f[MAXN][MAXN];
int go[MAXN][MAXN][MAXN];//go[i][j]选取元素集 
int cnt=2; 
void dfs(int p,bool sign){
    if(col[p]&&col[p]!=cnt^sign){
        cout<<"No solution";
        exit(0);//结束所有程序 
    }
    if(col[p]) return;
    col[p]=cnt^sign;
    for(int i=1;i<=n;i++)
        if(con[p][i])
            dfs(i,!sign);
    return;
}//染色 
void build(){
    for(int i=1;i<=n;i++)
        if(!col[i]){
            dfs(i,0);
            cnt+=2;
        }
    for(int i=1;i<=n;i++)
        sum[col[i]]++;//统计 
    return;
}
void dp(){
    f[0][0]=true;
    for(int i=2;i<cnt;i++)
        for(int j=i/2*2-2;j<=i/2*2-1;j++)
            for(int k=0;k<=n;k++){
                if(f[j][k]){
                    f[i][k]=true;
                    //go[i][k]=go[j][k];
                    for(int t=1;go[j][k][t];t++)
                        go[i][k][t]=go[j][k][t];
                }
                else if(k>=sum[i]&&f[j][k-sum[i]]){
                    f[i][k]=true;
                    int t=1;
                    while(go[j][k-sum[i]][t]){
                        go[i][k][t]=go[j][k-sum[i]][t];
                        t++;
                    }
                    if(t==1)
                        go[i][k][1]=i;
                    else
                        go[i][k][t]=i;
                }
            }
    return;
}
void print(){
    int res=0;
    for(int i=1;i<=n;i++)
        if(vis[col[i]]) res++;
    cout<<res<<" ";
    for(int i=1;i<=n;i++)
        if(vis[col[i]]) cout<<i<<" ";
    cout<<endl;
    cout<<n-res<<" ";
    for(int i=1;i<=n;i++)
        if(!vis[col[i]]) cout<<i<<" ";
    return;
}//输出答案 
void find(){
    for(int j=n/2;j>=1;j--)//找答案 
        for(int i=(cnt-1)^1;i<cnt;i++)
            if(f[i][j]){
                for(int t=1;go[i][j][t];t++)
                    vis[go[i][j][t]]=true;//标记 A 集合子集 
                print();
                return;
            }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            knw[i][j]=(i!=j);
    for(int i=1;i<=n;i++)
        while(cin>>u){
            if(u==0) break;
            knw[i][u]=false;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            con[i][j]=(i!=j&&(knw[i][j]||knw[j][i]));//con[i][j]: i,j 是否不同组 
    build();
    dp();
    find();
    return 0;
}