蒟蒻割点WA24分,大佬求解
查看原帖
蒟蒻割点WA24分,大佬求解
287411
_脑波_楼主2021/7/11 21:19
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int fh=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>'0'&&ch<'9')fh=(fh<<1)+(fh<<3)+(ch^48),ch=getchar();
	return fh;
}
const int N=1e5+5;
bool gd[N],gs;
int dfn[N],low[N],tim,root,v[N];
int head[N],esum,n,m,xx,yy;
struct edge{
	int to,next;
}e[N*2];
void add(int u,int v){
	++esum;
	e[esum].to=v;
	e[esum].next=head[u];
	head[u]=esum;
}
void tarjan(int u,int fa){
	low[u]=dfn[u]=++tim;
	int child=0;
	for(int i=head[u];i;i=e[i].next){
		if(e[i].to==fa)continue;
		if(!dfn[e[i].to]){
			tarjan(e[i].to,u);
			low[u]=min(low[u],low[e[i].to]);
			if((fa!=0&&low[e[i].to]>=dfn[u]))gd[u]=1;
			++child;
		}
		else low[u]=min(low[u],dfn[e[i].to]);
	}
	if(fa==0&&child>1)gd[u]=1;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i=-~i){
		xx=read(),yy=read();
		add(xx,yy);
		add(yy,xx);
	}
	for(int i=1;i<=n;i=-~i){
		if(!dfn[i]){
			root=i;
			tarjan(i,0);
		}
	}
	for(int i=1;i<=n;i=-~i){
		if(gd[i]==1){
			++gs;
			v[gs]=i;
		}
	}
	sort(v+1,v+gs+1);
	printf("%d\n",gs);
	for(int i=1;i<=gs;i=-~i)printf("%d ",v[i]);
}

附上提交记录

2021/7/11 21:19
加载中...