求助12分
查看原帖
求助12分
335094
Lucifero楼主2020/12/9 20:21
#include <bits/stdc++.h>
using namespace std;
class Edge
{
public:
	int l,r,nextline;
}eline[1600000];
stack<int> dot;
int elast[40000],dfn[40000],below[40000],dis[40000],cut[40000],cnt;
int n,m,order,temp=1,ans;
void add(int u,int v)
{
	eline[temp].l=u;
	eline[temp].r=v;
	eline[temp].nextline=elast[u];
	elast[u]=temp,temp++;
}
void tarjan(int u,int father)
{
	int v,i;
	order++;
	dfn[u]=below[u]=order;
	dot.push(u);
	for(i=elast[u];i!=0;i=eline[i].nextline)
	{
		v=eline[i].r;
		if (dfn[v]==0)
		{
			tarjan(v,u);
			below[u]=min(below[u],below[v]);
		}
		else if (v!=father)
			below[u]=min(below[u],dfn[v]);
	}
	if (dfn[father]<=below[u])
	{
		cut[++cnt]=father;
		do
		{
			v=dot.top();
			dot.pop();
		}while(!dot.empty() && u!=v);
	}
}
int main()
{
	//【模板】割点(割顶)
	int x,y,i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	for(i=1;i<=n;i++)
		if (dfn[i]==0) tarjan(i,0);
	sort(cut+1,cut+cnt+1);
	for(i=1;i<=cnt;i++)
		if (cut[i]!=0) printf("%d\n",cut[i]);
}
2020/12/9 20:21
加载中...