wa了第八个点求调
查看原帖
wa了第八个点求调
502353
地府看门大爷楼主2021/11/18 21:36
#include<iostream>
#include<cstdio>
using namespace std;
int n;
struct edge
{
	int nt;
	int from;
	int to;
};
edge b[99100];
int hd[10001],c;
void add(int x,int y)
{
	c++;
	b[c].from =x;
	b[c].nt =hd[x];
	b[c].to =y;
	hd[x]=c;
}
int dsn[10001],low[10001],cnt;
int st[10000],sd;
int qlt[10001],qs;
bool in[10001];
edge b1[99100];
int hd1[10001],c1;
void add1(int x,int y)
{
	c1++;
	b1[c1].nt =hd1[x];
	b1[c1].to =y;
	hd1[x]=c1;
}
void tarjan(int x)
{
	dsn[x]=low[x]=cnt++;
	in[x]=1;
	st[++sd]=x;
	for(int i=hd[x];i;i=b[i].nt )
	{
		int to=b[i].to ;
		if(!dsn[to])
		{
			tarjan(to);
			low[x]=min(low[x],low[to]);
		}
		else if(in[to])
		{
			low[x]=min(low[x],dsn[to]);
		}
	}
	if(dsn[x]==low[x])
	{
		qs++;
		while(st[sd]!=x)
		{
			qlt[st[sd]]=qs;
			in[st[sd]]=0;
			st[sd]=0;
			sd--;
		}
		qlt[st[sd]]=qs;
		in[st[sd]]=0;
		st[sd]=0;
		sd--;
	}
}
int du[1010];
int chu[1001];
int du0,chu0;
int fg;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		while(t!=0)
		{
			add(i,t);
			scanf("%d",&t);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dsn[i]==0) tarjan(i);
	}
	for(int i=1;i<=c;i++)
	{
		int x=b[i].from ,y=b[i].to ;
		//cout<<x<<" "<<y<<endl;
		if(qlt[x]!=qlt[y])
		{
			add1(qlt[x],qlt[y]);
			du[qlt[y]]++;
			chu[qlt[x]]++;
		}
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<qlt[i]<<" ";
	}
	for(int i=1;i<=c1;i++)
	{
		cout<<b1[i].from <<" "<<b1[i].to <<endl;
	}*/
	for(int i=1;i<=qs;i++)
	{
		if(du[i]==0) du0++;
		if(chu[i]==0) chu0++;
	}
	if(qs==1) 
	{
		cout<<"1"<<endl;
		return 0;
	}
	cout<<du0<<endl;
	cout<<max(du0,chu0);
	return 0;
}

输出:4 7 整解:3 6

2021/11/18 21:36
加载中...