求救啊真不知道哪里写错了
查看原帖
求救啊真不知道哪里写错了
247269
MSqwq楼主2020/12/11 20:57

感觉是tarjan写错了
但是找不出错来

#include<bits/stdc++.h>
using namespace std;
int n;
int x,y;
struct qwe{
	int next,v;
}e[400010];
int k=0,elast[80010];
void add(int x,int y)
{
	e[++k].v=y;
	e[k].next=elast[x];
	elast[x]=k;
}
long long dfn[100010],low[100010],tot=0,scc,p[100010];

void tarjan(int x,int fa)
{
	int sum=0;
	dfn[x]=low[x]=tot++;
	int qwe;
	for(int i=elast[x];i;i=e[i].next)
	{
		qwe=e[i].v;
		//cout<<qwe<<" ";
		if(!dfn[qwe])
		{
			tarjan(qwe,fa);
			low[x]=min(low[x],low[qwe]);
			if(low[qwe]>=dfn[x]&&x!=fa)p[x]=1;
			
			if(x==fa)sum++;
		}

		low[x]=min(low[x],dfn[qwe]);
	}
	
	if(x==fa&&sum>=2)p[x]=1;
}
int dian,v[100010],o=1,ge_sum=0,ge,sum,ans;

void gedian(int x)
{
	v[x]=o;
	ge_sum++;
	int qwe;
	for(int i=elast[x];i;i=e[i].next)
	{
		qwe=e[i].v;
		if(p[qwe]&&v[qwe]!=o)
		{
			ge++;
			v[qwe]=o;
		}
		if(v[qwe]==0)gedian(qwe);
	}
}

void clean()
{
	o=1;
	ge_sum=0;
	ge=0;
	sum=0;
	ans=1;
	for(int i=0;i<100010;i++)
	{
		v[i]=0;
		low[i]=0;
		dfn[i]=0;
		p[i]=0;
		elast[i]=0;
	}
	k=0;
	dian=0;
}
int main()
{
	for(int k=1;;k++)
	{
		clean();
		cin>>n;
		if(n==0)return 0;
		for(int i=1;i<=n;i++)
		{
			cin>>x>>y;
			add(x,y);
			add(y,x);
			
			dian=max(max(x,y),dian);
		}
		
		for(int i=1;i<=dian;i++)if(!dfn[i])tarjan(i,i);
		
		
//		for(int i=1;i<=dian;i++)cout<<p[i]<<" ";
//		cout<<endl;
		for(int i=1;i<=dian;i++)
		{
			if(v[i]==0&&p[i]==0)
			{
				ge=0,sum=0;
				gedian(i);
				if(ge==0)
				{
					if(sum==1||sum==0)continue;
					ge_sum+=2;
					ans*=sum*(sum-1)/2;
				}
				if(ge==1)
				{
					ge_sum++;
					ans*=sum;					
				}
				
				o++;
			}

		}
		
		cout<<"Case "<<k<<": "<<ge_sum<<" "<<ans<<endl;
	}

	 
}

2020/12/11 20:57
加载中...