求助!36分,四个AC,五个RE,2个WA,我改不出来呜呜呜
查看原帖
求助!36分,四个AC,五个RE,2个WA,我改不出来呜呜呜
614984
NNNNzh楼主2022/4/29 02:49
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int dfn[N],cnt,head[N],low[N];
int index,tot,vis[N],col[N];
int colnum=0,stac[N];
int n;
int ins[N],out[N];
struct e{
	int next,v,u;
}edge[10005];
void add(int u,int v)
{
	edge[++cnt].v=v;
	edge[cnt].u=u;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	vis[x]=1;
	stac[++index]=x;
	for(int i=head[x];i;i=edge[i].next)
	{
		int v=edge[i].v;
		if(!dfn[v])
		{
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(vis[v])
		{
			low[x]=min(low[x],dfn[v]);
		}
		if(low[x]==dfn[x])
		{
			colnum++;int tmp;
		    do{
		    	tmp=stac[index--];
				vis[tmp]=0;
				col[tmp]=colnum;
			}while(tmp!=x);
		}
	}
}
int main()
{
	cin>>n;	int x;
	for(int i=1;i<=n;i++)
	{
	
		cin>>x;
		while(x!=0)
		{
			add(i,x);
			cin>>x;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i);
	}
for(int i=1;i<=n;i++)
{
	for(int j=head[i];j;j=edge[j].next)
	if(col[i]!=col[edge[j].v])
	{
		ins[col[edge[i].v]]++;
		out[col[i]]++;
	}
}
	int inc=0,ouc=0;
	for(int i=1;i<=colnum;i++)
	{
	    if(ins[i]==0)
	    {
	    	   inc++;
		}
	    if(out[i]==0)
	    {
	    	    ouc++;
		}
	}
	if(colnum==1)
	printf("1\n0\n");
	else
	{
		printf("%d\n",inc);
		printf("%d\n",max(inc,ouc)); 
	 } 
}


2022/4/29 02:49
加载中...