/*
先是建图,跑一次缩点
建立一个最初的阵营
加上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;
}
标签:cnt,认识,int,ans,阵营,计数问题,sat
From: https://www.cnblogs.com/basicecho/p/17535551.html