68分TLE求助
查看原帖
68分TLE求助
246099
dalao_see_me楼主2021/2/4 08:43

RT,第二个点自己跑是0.3s,洛谷上就T了。

code:

#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define getchar() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
const int N=2e4+6;
int iscut[N],lst[N],low[N],dfn[N];
struct edge{
	int to,nxt;
}e[N<<3];
int n,m,cnt,indexx;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
inline void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].nxt=lst[u];
	lst[u]=cnt;
}
inline void Tarjan(int x,int dad){
	dfn[x]=low[x]=++indexx;
	int sons=0;
	for(int i=lst[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(!dfn[to]){
			Tarjan(to,dad);
			low[x]=min(low[x],low[to]);
			if(dfn[x]<=low[to]&&x!=dad)iscut[x]=1;
			if(x==dad)sons++;
		}
		low[x]=min(low[x],dfn[to]);
	}
	if(sons>1&&x==dad)iscut[x]=1;
}
int main(){
//	freopen("P3388_2.in","r",stdin);
//	freopen("P3388_2.out","w",stdout);
	memset(dfn,0,sizeof(dfn));
	memset(iscut,0,sizeof(iscut));
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])Tarjan(i,i);
	cnt=0;
	for(int i=1;i<=n;i++)
		if(iscut[i])cnt++;
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++)
		if(iscut[i])printf("%d ",i);
	return 0;
}
2021/2/4 08:43
加载中...