六十三分求助
查看原帖
六十三分求助
47205
jzy_go楼主2020/8/29 08:45
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e5;
const int MAXM=1e5;
struct node{
	int u,v,w,next;
}e[MAXM],e2[MAXM];
int head[MAXN],head2[MAXN];
int cnt,cnt2;
void add(int u,int v,int w)
{
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void add2(int u,int v,int w)
{
	e2[++cnt2].u=u;
	e2[cnt2].v=v;
	e2[cnt2].w=w;
	e2[cnt2].next=head2[u];
	head2[u]=cnt2;
}
int dfn[MAXN];
int low[MAXN];
int s[MAXN];
int tot;
int top;
int col;
int co[MAXN];
int all[MAXN];
int f[MAXN];
void tarjan(int u)
{
	dfn[u]=low[u]=++tot;
	s[++top]=u;
	for(int i=head[u];i;i=e[i].next)
	{
		if(dfn[e[i].v]==0)
		{
			tarjan(e[i].v);
			low[u]=min(low[u],low[e[i].v]);
		}
		else
		low[u]=min(low[u],dfn[e[i].v]);
	}
	if(low[u]==dfn[u])
	{
		co[u]=++col;
		while(s[top]!=u)
		{
			co[s[top]]=col;
			top--;
			all[col]++;
		}
		top--;
		all[col]++;
	}
}
int lj[101][101];
int init[MAXN];
int outit[MAXN];
void dfs(int u,int fa)
{
	f[u]=fa;
	for(int i=head2[u];i;i=e2[i].next)
	if(!f[e[i].v])
	dfs(e[i].v,fa);
}
int main()
{
	int n=read();
	int x;
	for(int i=1;i<=n;i++)
	{
		x=read();
		while(x!=0)
		{
			add(i,x,1);
			x=read();
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)
		tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=e[j].next)
		{
			if(co[i]!=co[e[j].v])
			{
				if(!lj[co[i]][co[e[j].v]])
				{
					add2(co[i],co[e[j].v],1);
					lj[co[i]][co[e[j].v]]=1;
					init[co[e[j].v]]++;
					outit[co[i]]++;
				}
	 		}
		}
	}
	int ans1=0;
	for(int i=1;i<=col;i++)
	if(init[i]==0)
	{
		dfs(i,i);
		ans1++;
	}
	if(col==1)
	{
		cout<<1<<endl<<"0"<<endl;
		return 0;
	}
	cout<<ans1<<endl;
	int ans2=0;
	for(int i=1;i<=col;i++)
	{
		if(outit[i]==0)
		{
			int flag=0;
			for(int j=head2[i];j;j=e2[j].next)
			{
				if(e[j].v==f[i])
				{
					flag=1;
					break;
				}
			}
			if(!flag)
			ans2++;
		}
	}
	cout<<ans2<<endl;
	return 0;
}

2020/8/29 08:45
加载中...