80分求助
查看原帖
80分求助
290959
聊机楼主2021/6/14 22:09

RT,不知道为什么第11个数据会少输出一个割点。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int k=0;bool f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
	while(isdigit(ch)){k=(k<<1)+(k<<3)+(ch^48);ch=getchar();}
	return f?k:~k+1;
}
const int N=2e4+2,M=1e5+2;
struct Edge{
	int to,next;
}e[M*2];
int h[M*2],tot;
inline void add(int u,int v){
	e[++tot].to=v;
	e[tot].next=h[u];
	h[u]=tot;
}
int n,m;
int dfn[N],low[N],t[N];
int in[N],st[N],siz,cnt;
void Tarjan(int l,int x){
	dfn[x]=low[x]=++tot;
	in[x]=1;st[++siz]=x;
	for(int i=h[x];i;i=e[i].next)
	{
		if(e[i].to==l) continue;
		if(!dfn[e[i].to]) Tarjan(x,e[i].to);
		if(in[e[i].to]) low[x]=min(low[x],low[e[i].to]);
	}
	if(dfn[x]==low[x]) {
		t[x]=++cnt;
		while(st[siz]!=x) {
			t[st[siz]]=cnt;
			in[st[siz--]]=0;
		}
		in[st[siz--]]=0;
	}
}
int main(){
    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(0,i);
	queue<int>ans;
	for(int i=1;i<=n;i++) 
	{
		int p=e[h[i]].to;
		for(int j=h[i];j;j=e[j].next)
		    if(t[e[j].to]!=t[p]) {
		    	ans.push(i);break;
			}
	}
	printf("%d\n",ans.size());
	while(ans.size()) {
		printf("%d ",ans.front());ans.pop();
	} 
	return 0;
}
2021/6/14 22:09
加载中...