题目链接：

题目

#67. 新年的毒瘤

问题描述

辞旧迎新之际，喜羊羊正在打理羊村的绿化带，然后他发现了一棵长着毒瘤的树。

这个长着毒瘤的树可以用 nn 个结点 mm 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点，即删掉这个结点和与之相邻的边之后，这个图会变为一棵树。树也即无简单环的无向连通图。

现在给你这个无向图，喜羊羊请你帮他求出所有毒瘤结点。

输入

第一行两个正整数 n,mn,m，表示有 nn 个点 mm 条边。保证 n≥2n≥2。

接下来 mm 行，每行两个整数 v,uv,u，表示 vv 和 uu 之间有一条无向边。1≤v,u≤n1≤v,u≤n。保证没有重边和自环。

n,m<=10^5

输出

第一行一个正整数 nsns，表示这个图中有 nsns 个结点是毒瘤。

接下来一行，共 nsns 个整数，每个整数表示一个毒瘤结点的编号。请按编号从小到大的顺序输出。

数据保证图中至少存在一个毒瘤结点。

样例

input

6 6

1 2

1 3

2 4

2 5

4 6

5 6

output

3

4 5 6

题解

如果一个点不是割点（说明去掉它之后原图还是联通）并且删除它之后边剩下n-2条，则它是毒瘤节点。

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<string>

#include<queue>

using namespace std;

const int maxn = 1e5+10;

int n, m;

vector<int> G[maxn];

int pre[maxn], low[maxn], dfs_clock,iscut[maxn];

int dfs(int u, int fa) {

	int lowu = pre[u] = ++dfs_clock;

	int child = 0;

	for (int i = 0; i < G[u].size(); i++) {

		int v = G[u][i];

		if (!pre[v]) {

			child++;

			int lowv = dfs(v, u);

			lowu = min(lowu, lowv);

			if (lowv >= pre[u]) {

				iscut[u] = true;

			}

		}

		else if (pre[v] < pre[u] && v != fa) {

			lowu = min(lowu, pre[v]);

		}

	}

	if (fa < 0 && child == 1) iscut[u] = 0;

	low[u] = lowu;

	return lowu;

}

void init() {

	for (int i = 0; i <= n; i++) G[i].clear();

	memset(pre, 0, sizeof(pre));

	memset(low, 0, sizeof(low));

	memset(iscut, 0, sizeof(iscut));

	dfs_clock = 0;

}

int main() {

	int tc;

	scanf("%d%d", &n, &m);

	init();

	for (int i = 0; i < m; i++) {

		int u, v;

		scanf("%d%d", &u, &v), u--, v--;

		G[u].push_back(v);

		G[v].push_back(u);

	}

	dfs(0, -1);

	vector<int> ans;

	for (int i = 0; i < n; i++) {

		if (!iscut[i] && m - G[i].size() == n - 2) {

			ans.push_back(i + 1);

		}

	}

	sort(ans.begin(), ans.end());

	printf("%d\n", ans.size());

	for (int i = 0; i < ans.size() - 1; i++) printf("%d ", ans[i]);

	printf("%d\n", ans[ans.size() - 1]);

	return 0;

}