62pts求调
查看原帖
62pts求调
777881
hengda909楼主2025/7/21 16:44
#include <bits/stdc++.h>
using namespace std;
const int NR=5005;
int n,k[NR],o,ans[NR],g[NR],w[NR],ne[NR],ts[NR],tx[NR],c1=0,c2=0;
bitset<NR> a[NR],v[NR];
void Dfs1(int u,int rt){
	v[rt][u]=1;
	for(int i=1;i<=n;i++)
		if(a[u][i]&&!v[rt][i])
			Dfs1(i,rt);
}
int dfn[NR<<1],s[NR<<1],tp=0,sz[NR<<1],ins[NR<<1],low[NR<<1],sc=0,scc[NR<<1],dfc=0,hvas=0;
void Pop(){
	scc[s[tp]]=sc; sz[sc]++; ins[s[tp]]=0;tp--;
}
void Tarjan(int x,int id){
	dfn[x]=low[x]=++dfc; s[++tp]=x; ins[x]=1;
	for(int i=1;i<=n;i++){
		if(i==id)continue;
		if(a[i][id]&&x<=n){
			int v=i+n,nid=i;
			if(!dfn[v]) { 
				Tarjan(v,nid);
				low[x]=min(low[x],low[v]);
			}
			if(ins[v]) low[x]=min(low[x],low[v]);
		}if(!a[i][id]&&x>n){
			int v=i,nid=i;
			if(!dfn[v]) { 
				Tarjan(v,nid);
				low[x]=min(low[x],low[v]);
			}
			if(ins[v]) low[x]=min(low[x],low[v]);
		}
	}
	if(dfn[x]==low[x]){
		++sc;
		while(s[tp]!=x)Pop(); Pop();
	}
} 
void P1(){
	
    int ans=1;
    for(int i=1;i<=c1;i++){
        int x=ne[i],cnt=0;
        Dfs1(x,x);
        for(int j=1;j<=c2;j++){
            int y=w[j];
            if(v[x][y]){
                cnt++;
                if(cnt>1){
                    ts[i]=-1; break;
                }
                ts[i]=y;
            }
        }
    }
    for(int i=1;i<=c2;i++){
        int x=w[i],cnt=0;
        Dfs1(x,x);
        for(int j=1;j<=c1;j++){
            int y=ne[j];
            if(!v[x][y]){
                cnt++;
                if(cnt>1){
                    tx[i]=-1; break;
                }
                tx[i]=y;
            }
        }
    }
    if(c1>1)
    	for(int i=1;i<=c1;i++)
        	if(!ts[i])
            	ans++;
    if(c2>1)
   		for(int i=1;i<=c2;i++)
    		if(!tx[i])
            	ans++;
    for(int i=1;i<=c1;i++)
        for(int j=1;j<=c2;j++)
            if((ts[i]==w[j]||!ts[i])&&((tx[j]==ne[i]||!tx[j])))
                ans++;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k[i];
		while(k[i]--){
			cin>>o;
			a[i][o]=a[o][i]=1;
		}
	}
	for(int i=1;i<=2*n;i++){
		if(!dfn[i])
			Tarjan(i,(i-1)%n+1);
	}
	for(int i=1;i<=n;++i){
		if(scc[i]==scc[i+n]){
			cout<<0;return 0;
		}
		if(scc[i]<scc[i+n]) ans[i]=0;
		else ans[i]=1;
	}
	for(int i=1;i<=n;i++){
        if(!ans[i]) ne[++c1]=i;
        else w[++c2]=i;
    }
    if(!c1||!c2){
    	cout<<0;
    	return 0;
	}
	P1();
	cout<<ans;
	return 0;
}
2025/7/21 16:44
加载中...