萌新tarjan36分求助
查看原帖
萌新tarjan36分求助
549846
dpACerFXing楼主2023/6/21 16:41
# include<iostream>
# include<algorithm>
# include<cmath>
# include<iomanip>
# define endl "\n"
using namespace std;
const int maxn=20001;
struct Node{
	int u, v, next;
}edge[100001]; 
int n, m, cnt=0, head[maxn];
int dfn[maxn], low[maxn], num=0;
int res[maxn], sum=0;
void add(int u, int v) {
	cnt++;
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void tarjan(int u, int fa) {
	dfn[u]=low[u]=++num;
	for(int i=head[u]; i; i=edge[i].next) {
		int v=edge[i].v;
		if(v==fa) continue;
		else if(dfn[v]==0) {
			tarjan(v, u);
			if(dfn[u]<=low[v] && u!=1) sum++, res[sum]=u;
			low[u]=min(low[u], low[v]);
		} else low[u]=min(low[u], dfn[v]);
	}
}
int main(){
	cin >> n >> m;
	while(m--) {
		int u, v;
		cin >> u >> v;
		add(u, v); add(v, u);
	} 
	tarjan(1, 0);
	cout << sum << endl;
	for(int i=1; i<=sum; i++)
	    cout << res[i] << endl;
	return 0;
}

qwq

2023/6/21 16:41
加载中...