莫名RE求大佬帮忙看看
查看原帖
莫名RE求大佬帮忙看看
202224
asd0342楼主2020/8/5 11:50
#include<bits/stdc++.h>
#define pu(i,j) i+n*j
using namespace std;
int n,num[2],numft[2];
int tot1,tot2,cnt;
int head[2][10010];
int z[10010],f[10010],fz[10010],belong[10010];
vector<int> frd[10010],ft[10010],dis_frd[10010];
bool vis[10010];
long long sum;
struct EDGE
{
	int v,nxt;
}g[2][2500010];
void add1(int u,int v)
{
	g[0][tot1].v=v;
	g[0][tot1].nxt=head[0][u];
	head[0][u]=tot1++;
}
void add2(int u,int v)
{
	g[1][tot2].v=v;
	g[1][tot2].nxt=head[1][u];
	head[1][u]=tot2++;
}
void addedge(int u,int v)
{
	add1(u,v);
	add2(v,u);
}
void intl()
{
	tot1=0,tot2=0;
	memset(head,-1,sizeof(head));
}
void dfs1(int x)
{
	vis[x]=1;
	for(int i=head[1][x],v;~i;i=g[1][i].nxt)
		if(!vis[v=g[1][i].v]) dfs1(v);
	z[++cnt]=x;
	fz[x]=cnt;
}
void dfs2(int x,int y)
{
	f[x]=y;
	vis[x]=0;
	for(int i=head[0][x],v;~i;i=g[0][i].nxt)
		if(vis[v=g[0][i].v]) dfs2(v,y);
}
void jdg()
{
	for(int i=1;i<=2*n;i++)
		if(f[pu(i,0)]==f[pu(i,1)])
		{
			printf("0");
			return;
		}
	for(int i=1;i<=n;i++)
	{
		if(fz[pu(i,0)]<fz[pu(i,1)])
			belong[i]=1,num[1]++;
		else
			belong[i]=0,num[0]++;
	}
	if(num[0]&&num[1]) sum++;
	for(int i=1;i<=n;i++)
	{
		if(belong[i])
		{
			for(int j=0;j<frd[i].size();j++)
				if(!belong[frd[i][j]])
					ft[i].push_back(frd[i][j]);
		}
		else
		{
			for(int j=0;j<dis_frd[i].size();j++)
				if(belong[dis_frd[i][j]])
					ft[i].push_back(dis_frd[i][j]);
		}
		if(ft[i].size()==0) numft[belong[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(ft[i].size()==1&&ft[ft[i][0]].size()==0)
			sum++;
		if(ft[i].size()==0&&num[belong[i]]>=2)
			sum++;
	}
	sum+=numft[0]*numft[1];
	printf("%lld",sum);
}
int main()
{
	intl();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int m;
		scanf("%d",&m);
		memset(vis,0,sizeof(vis));
		vis[i]=1;
		for(int j=1;j<=m;j++)
		{
			int p;
			scanf("%d",&p);
			frd[i].push_back(p);
			vis[p]=1;
			addedge(pu(i,0),pu(p,1));
		}
		for(int j=1;j<=n;j++)
			if(!vis[j])
			{
				dis_frd[i].push_back(j);
				addedge(pu(j,1),pu(i,0));
			}
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=2*n;i++)
		if(!vis[i]) dfs1(i);
	for(int i=2*n;i>=1;i--)
		if(vis[z[i]]) dfs2(z[i],z[i]);
	jdg();
	return 0;
}//1后勤 0同谋 

蒟蒻想不明白错哪了QWQ

2020/8/5 11:50
加载中...