P3388 割点模板 WA on #2蒟蒻求助
查看原帖
P3388 割点模板 WA on #2蒟蒻求助
1086931
bishenke_2008楼主2024/7/15 11:44

神犇初学tarjan 不知道哪里错了
恳请各位大佬帮帮忙 谢谢!!!

#include<bits/stdc++.h>
using namespace std;
#define next Next
const int N=100005;

int n,m;
int cnt=1;
int head[N];
int next[N],ver[N];
int num=0;
int root;
int dfn[N],low[N];
int ans=0;
bool cut[N];

void add(int u,int v){
	next[cnt]=head[u];
	ver[cnt]=v;
	head[u]=cnt++;
}

void tarjan(int x){
	dfn[x]=low[x]=++num;
	int flag=0; 
	for(int i=head[x];i;i=next[i]){
		int y=ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if((x!=root||flag>1)&&!cut[x]){
					cut[x]=true;
					ans+=cut[x];
				}	
			}
				
		}
		else low[x]=min(low[x],dfn[y]);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	
	for(int i=1;i<=n;i++)
		if(!dfn[i]){
			root=i;
			tarjan(i);
		}
	
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++)
		if(cut[i]) cout<<i<<' ';
	return 0;
}
2024/7/15 11:44
加载中...