RT

用的向量存边

P3388 【模板】割点（割顶）

记录详情

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 3;
const int M = 1e5 + 3;//没用

int n, m;
int root;//记录根点，根要特判
vector<int> v[N];//向量记录边   v[i]存储了点i的所有出边 所指的对面的点
int ind, child;//ind用于dfn计数  child用于记录根点有几个儿子 如果只有1个则根点不是割点
int dfn[N], low[N];
bool gd[N];//gd[i]表示点i是否是割点
int cnt;//记录割点总数量

void dfs(int x, int father)
{
	dfn[x] = low[x] = ++ind;
	for (int i=0; i<v[x].size(); ++i)//遍历点x的出边
	{
		int y = v[x][i];//该出边所指向的点y
		if (!dfn[y])//如果点y还没搜过当然也不可能是点x的父亲 因为dfs顺序是从根点出发 从祖辈到儿辈
		{
			child++;//点y是x的一个儿子
			dfs(y, x);//以点x为父亲搜点y
			low[x] = min(low[x], low[y]);
			if (x!=root && low[y]>=dfn[x])//
				cnt += gd[x] = 1;//是割点
			else if (x==root && child == 2)//特判根
				cnt += gd[x] = 1;
		}
		else if (y != father)//如果搜过又不是父亲，那点y就是点x的祖辈
			low[x] = min(low[x], dfn[y]);
	}
}
int main()
{
	cin >> n >> m;
	for (int i=1, x, y; i<=m; ++i) {
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i=1; i<=n; ++i)//因为可能不连通所以要把每个点都搜一遍
		if (!dfn[i]) {//如果搜过了当然就不搜了
			root = i;//搜索前更新根为出发点
        child = 0;//重置根点儿子的数量
			dfs(i, root);
		}
	cout << cnt << endl;
	for (int i=1; i<=n; ++i)//遍历所有点
		if (gd[i])//如果是割点
			printf("%d ", i);
	return 0;
}