思路和题解一样，我这里存快的方法比较特别，希望 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;
}