求调
查看原帖
求调
356510
wsnxsf楼主2022/8/21 20:16
#include<bits/stdc++.h>
#define int long long 
using namespace std;
struct node{
	int from,to,next;
}edge[100005]; 
int m,n,tot,node[20005],dfn[20005],low[20005],k=0,cut[20005],tt;
bool stck[200005];
void make_edge(int x,int y){
	edge[++tot].from=x;
	edge[tot].to=y;
	edge[tot].next=node[x];
	node[x]=tot; 
}
void make_edge_two(int x,int y){
	make_edge(x,y),make_edge(y,x);
}
void tarjan(int now,int fa){
	dfn[now]=low[now]=++k;
	int ch=0;
	for(int i=node[now];i;i=edge[i].next){
		/*if(now==1){
			cout<<edge[i].from<<' '<<edge[i].to<<endl;
		}*/
		int t=edge[i].to;
		if(!dfn[t]){
			//cout<<now<<'*'<<t<<endl;
			tarjan(t,fa);
			low[now]=min(low[now],low[t]);
			if(dfn[now]<=low[t]&&now!=fa&&!stck[now]){
				stck[now]=true;
				cut[++tt]=now;
			}
			if(now==fa){
				ch++;
			}
		}
		low[now]=min(low[now],dfn[t]);
	}
	/*if(now==1){
		cout<<now<<' '<<fa<<' '<<ch<<' '<<stck[now]<<endl;
	}*/
	if(now==fa&&ch>=2&&!stck[now]){
		stck[now]=true;
		cut[++tt]=now;
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int from,to;
		cin>>from>>to;
		make_edge_two(from,to);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			tarjan(i,i);
		} 
	}
	/*for(int i=1;i<=n;i++){
		cout<<i<<' '<<dfn[i]<<' '<<low[i]<<endl; 
	}*/
	sort(cut+1,cut+tt+1);
	cout<<tt<<endl;
	for(int i=1;i<=tt;i++){
		cout<<cut[i]<<' ';
	}
	return 0;
}

68分 错2,3,5,9号点

2022/8/21 20:16
加载中...