sat计数问题-526互联

/*
先是建图，跑一次缩点
建立一个最初的阵营
加上0代表认识，1代表不认识
ans=0

因为划分了两个独立的阵营，所以一次是只能交换一个人的 

如果对方阵营我只认识一个，并且我认识的哪一个可以来到我的阵营，那么就将两者进行交换（0，1） 
 
如果对方阵营的我都不敌对，或不认识，那我就可以直接过去（0直接过去一个人） 
 
 
这个统计的问题，也就是把所有的情况的列举出来了 
*/

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define hr cout<<"-------------------------------------\n"
#define br cout<<'\n';
const int N=5005; 

int n;
bool g[N][N];

int h[N<<1],ne[N*N],e[N*N],tot;
void add(int a,int b) {
	e[++tot]=b; ne[tot]=h[a]; h[a]=tot;
}

int dfn[N<<1],low[N<<1],cnt;
int color[N<<1],scnt;
stack<int>st;
bool vis[N<<1];

void tarjan(int now) {
	dfn[now]=low[now]=++cnt;
	st.push(now);
	vis[now]=1;
	for(int i=h[now];i;i=ne[i]) {
		int to=e[i];
		if(dfn[to]==0) {
			tarjan(to);
			low[now]=min(low[now],low[to]);
		} 
		else if(vis[to])low[now]=min(low[now],dfn[to]);
	}
	if(dfn[now]==low[now]) {
		scnt++;
		while(1) {
			int k=st.top();st.pop();vis[k]=0;
			color[k]=scnt;
			if(k==now)break;
		}
	}
}

//认识的，不认识的 
int c1[N],c2[N],cnt1=0,cnt2=0;
int match[N],f[N];
bool t[N];

void calc() {
	for(int i=1;i<=n;i++) {
		if(color[i]==color[i+n]) {
			cout<<"0\n";
			return ;
		}
		if(color[i]<color[i+n])c1[++cnt1]=i,t[i]=1;
		else c2[++cnt2]=i;
	}
	int ans=(cnt1&&cnt2);
	for(int i=1;i<=cnt1;i++)for(int j=1;j<=cnt2;j++)//判断对面的人我是否认识 
		if(g[c1[i]][c2[j]])f[c1[i]]++,match[c1[i]]=c2[j];
	for(int i=1;i<=cnt2;i++)for(int j=1;j<=cnt1;j++)//判断对面的人我是否为不认识 
		if(g[c2[i]][c1[j]]==0)f[c2[i]]++,match[c2[i]]=c1[j];
	for(int i=1;i<=n;i++)if(f[i]==1&&f[match[i]]==0)ans++;//对面这样的只有一个，并且可以过来 
	for(int i=1;i<=n;i++)if(f[i]==0)
		if((t[i]&&cnt1>1)||(t[i]==0&&cnt2>1))ans++;//直接取到对方的阵营就可以了 
	cout<<ans<<'\n';
}

void solve() {
	cin>>n;
	for(int i=1,cnt,x;i<=n;i++) {
		cin>>cnt;
		while(cnt--)cin>>x,g[i][x]=1;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
		if(i!=j) {
			if(g[i][j])add(i+n,j);
			else add(i,j+n);
		}
	for(int i=1;i<=2*n;i++)if(dfn[i]==0)tarjan(i);
	calc();
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}