36分求助
查看原帖
36分求助
285414
Swiftie_wyc22楼主2022/8/17 19:44
#include <bits/stdc++.h>

using namespace std;

int n, m, root;
vector<int>e[20000];
int num[20000], low[20000], flag[20000], id; // 用index进行时间戳的递增,num是时间戳,low是最小访问的时间戳

void dfs(int cur, int father)
{
	int child = 0;
	//child用来记录在生成树中当前顶点cur的儿子个数
	id++;
	num[cur]=id; // 当前顶点的时间戳
	low[cur] = id;
	
	for (int i = 0; i < (int)e[cur].size(); i++)
	{
		if (num[e[cur][i]] == 0) // 如果时间戳为0,说明顶点i还没有被访问过
		{
			child++;
			dfs(e[cur][i], cur);
			low[cur] = min(low[cur], low[e[cur][i]]); // 更新能访问到的最早的时间戳
			// 如果当前顶点不是根节点并且满足low[i]>=num[cur],则当前点为割点
			if (cur != root && low[e[cur][i]] >= num[cur]) flag[cur] = true;
			// 如果当前顶点是根节点,在生成树中根节点必须要有两个儿子,那么这个根节点才是割点
			if (cur == root && child == 2) flag[cur] = true;
		}
		else if (e[cur][i] != father)
		{
			// 否则如果顶点i曾经被访问过,并且这个顶点不是当前顶点cur的父亲,则说明此时的i为cur的祖先,因此需要更新当前节点cur能访问到最早顶点的时间戳
			low[cur] = min(low[cur], num[e[cur][i]]);
		}
	}
	return;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int x, y;
	cin >> n >> m;
	for (register int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for (register int i = 1; i <= n; i++)
		if (num[i] == 0)
			dfs(i, i);
	
	int cnt = 0;
	vector<int>ans;
	for(register int i = 1; i <= n; i++)
		if (flag[i])
		{
			cnt++;
			ans.push_back(i);
		}
	cout << cnt << endl;
	for (auto i : ans)
		cout << i << " ";
	cout << endl;
	return 0;
}
2022/8/17 19:44
加载中...