割点模板题WA76分求调!
查看原帖
割点模板题WA76分求调!
538715
ajhuhe楼主2022/7/21 20:34

这几天学习tarjan,做割点模板题结果WA76分,有哪位大佬知道为什么吗?

#include<bits/stdc++.h>
using namespace std;
int dfn[20002],low[20002],minn=1e9,fath[20001],cuts,cut[20001];
int x=0,cnt=0,n,m,ans,fathernode;
bool k,vis1[20001],vis2[20002],f[20002];
int h[20002];
struct node
{
	int to,t;
}e[200002];
void hit(int u,int v)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].t=h[u];
	h[u]=cnt;
}
stack <int> j;
void dfs(int u,int fa)
{
	dfn[u]=low[u]=++x;
	j.push(u);
	vis2[u]=vis1[u]=1;
	for(int i=h[u];i!=0;i=e[i].t)
	{
		if(vis1[e[i].to]==0)
		{
			dfs(e[i].to,u);
			low[u]=min(low[u],low[e[i].to]);	
		}
		else if(e[i].to!=fa)
		{
			low[u]=min(low[u],dfn[e[i].to]);
		}
	}
	if(dfn[fa]<=low[u])
	{
		if(fa!=fathernode&&fa&&fa<=n)
		{
			cuts++;
			cut[cuts]=fa;
		}
		while(!j.empty())
		{
			vis2[j.top()]=0;
			if(j.top()==u)
			{
				j.pop();
				break;
			}
			j.pop();
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		hit(a,b);
		hit(b,a);
		fath[a]=b;
		fath[b]=a;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis1[i])
		{
			fathernode=i;
			dfs(i,fath[i]);
		}
	}		
	cout<<cuts<<endl;
	sort(cut+1,cut+cuts+1);
	for(int i=1;i<=cuts;i++)
		cout<<cut[i]<<" ";
	return 0;
}
2022/7/21 20:34
加载中...