题目传送门
分析：
求团+独立集？这是什么？
冷静分析一波性质
假设我们找到了一个合法方案，其中团的大小为(S)，我们能否对(S)的大小进行变化
发现(S)的大小变化不可能超过(1)，如果有两个以上的人从独立集进入团，或者从团进入独立集，他们之间的连边关系会出现矛盾，导致不成立
于是只会出现三种情况了：
团里面的一个人进入独立集
独立集里面的一个人进入团
团和独立集里面各选一个人交换
这三种情况枚举方案加在一起，表明答案大小是在(n^2)级别的，暴力枚举就可以了
现在我们想办法求出一个合法方案
考虑2-sat，设(i)为在团，(i')为在独立集
如果(i,j)之间有连边，那么(i)在独立集中时，(j)就不能在独立集中，(i')向(j)连边
如果(i,j)之间无连边，那么(i)在团中时，(j)就不能在团中，(i)向(j')连边
跑一边2-sat判一下是否合法，然后缩点反向建图求方案
剩下的就是暴力枚举了（写得没什么技术含量）
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<map>
#include<bitset>
#include<string>
#define maxn 10005
#define MOD 1000000007
using namespace std;
inline long long getint()
{
long long num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int n;
bool vis[maxn],w[maxn>>1][maxn>>1];
vector<int>G[maxn],scc[maxn],V[maxn];
int dfn[maxn],low[maxn],sccno[maxn],clc,scccnt;
int stk[maxn],tp;
int d[maxn],c[maxn],sz1,sz2,p1[maxn],p2[maxn],ans;
inline void tarjan(int u)
{
dfn[u]=low[u]=++clc;stk[++tp]=u;
for(int i=0,v;i<G[u].size();i++)
if(!dfn[v=G[u][i]])tarjan(v),low[u]=min(low[u],low[v]);
else if(!sccno[v])low[u]=min(low[u],dfn[v]);
if(dfn[u]==low[u])
{
scccnt++;
while(1)
{
sccno[stk[tp]]=scccnt;
scc[scccnt].push_back(stk[tp]);
if(stk[tp--]==u)break;
}
}
}
inline void toposort()
{
queue<int>Q;
for(int i=1;i<=scccnt;i++)if(!d[i])Q.push(i);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=0;i<scc[u].size();i++)if(!vis[((scc[u][i]-1)^1)+1])vis[scc[u][i]]=1;
for(int i=0;i<V[u].size();i++)if(!(--d[V[u][i]]))Q.push(V[u][i]);
}
}
int main()
{
n=getint();
for(int i=1;i<=n;i++)
{
int tmp=getint();
while(tmp--)w[i][getint()]=1;
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)
if(w[i][j])G[2*i].push_back(2*j-1);
else G[2*i-1].push_back(2*j);
for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)if(sccno[2*i]==sccno[2*i-1]){printf("0
");return 0;}
for(int i=1;i<=2*n;i++)for(int j=0;j<G[i].size();j++)
if(sccno[i]!=sccno[G[i][j]])V[sccno[G[i][j]]].push_back(sccno[i]),d[sccno[i]]++;
toposort();
for(int i=1;i<=n;i++)
if(vis[i*2-1])c[i]=1,sz1++;
else c[i]=2,sz2++;
if(sz1&&sz2)ans++;
for(int i=1;i<=n;i++)
if(c[i]&1)
{
bool p=0;
for(int j=1;j<=n;j++)if(c[j]==2&&w[i][j]){p=1;break;}
if(!p&&sz1>1)ans++,p1[i]=1;
}
else
{
bool p=0;
for(int j=1;j<=n;j++)if(c[j]==1&&!w[i][j]){p=1;break;}
if(!p&&sz2>1)ans++,p2[i]=1;
}
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
if((p2[i]&&p1[j])||(p1[i]&&p2[j]))ans++;
printf("%d
",ans);
}
