割点模版求调,全WA,悬赏关注,谢谢!
查看原帖
割点模版求调,全WA,悬赏关注,谢谢!
546681
lcbridgeAK CSP-S楼主2023/4/7 20:03
#include <bits/stdc++.h>
using namespace std;
const int MAXN=20005;
const int MAXM=100005;
vector <int> g[MAXM];
int n,m;
int dfn[MAXN],low[MAXN],cnt,ans,prt[MAXN],root;
bool pd[MAXN];
void Tarjan(int u){
	int soncnt=0;
	dfn[u]=low[u]=++cnt;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!dfn[v]&&prt[u]!=v){
			prt[v]=u;
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=low[u]){
				if(!pd[u]){
					ans++;
					pd[u]=1;
				}
				if(dfn[u]==1){
					root=u;
					soncnt++;
				}
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(soncnt==1){
		ans--;
		pd[root]=0;
	}
}
int main(){
	//freopen("P3388_1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)if(pd[i])printf("%d ",i);
	return 0;
}
2023/4/7 20:03
加载中...