tarjan求割点求助
查看原帖
tarjan求割点求助
375350
zhouyujie楼主2022/12/10 15:22

76puts76puts求助

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4 + 5;
vector<int> G[MAXN];
int n, e, root;
int t = 0;
int dfn[MAXN], low[MAXN];
int point_list[MAXN];
int P = 0;
void tarjan(int i) {
	dfn[i] = low[i] = ++t;
	int count = 0;
	for(int j = 0; j < G[i].size(); j++) {
		int v = G[i][j];
		if(!dfn[v]) {
			tarjan(v);
			low[i] = min(low[i], low[v]);
			if(low[v] >= dfn[i]) {
				count++;
				if(i != root || count > 1) {
					point_list[++P] = i;
				}
			}
		}else low[i] = min(low[i], dfn[v]);
	}
}
int main() {
	cin >> n >> e;
	for(int i = 1; i <= e; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) {
		if(dfn[i] == 0) {
			root = i;
			tarjan(i);
		}
	}
	cout << P << endl;
	sort(point_list + 1, point_list + P + 1);
	for(int i = 1; i <= P; i++)
		cout << point_list[i] << " ";
	return 0; 
}
2022/12/10 15:22
加载中...