洛谷3388 【模板】割点（割顶）

一道找割点模板

原题链接

(tarjan)找割点模板，不解释。

#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
int fi[N], di[N << 1], ne[N << 1], dfn[N], low[N], an[N], l, r, ti;
bool v[N];
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c < '0' || c > '9'; c = getchar())
		p |= c == '-';
	for (; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + (c - '0');
	return p ? -x : x;
}
inline void add(int x, int y)
{
	di[++l] = y;
	ne[l] = fi[x];
	fi[x] = l;
}
inline int minn(int x, int y)
{
	return x < y ? x : y;
}
void tarjan(int x)
{
	int i, y, g = 0;
	dfn[x] = low[x] = ++ti;
	for (i = fi[x]; i; i = ne[i])
	{
		y = di[i];
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = minn(low[x], low[y]);
			if (low[y] >= dfn[x])
			{
				g++;
				if ((x ^ r) || g > 1)
					v[x] = 1;
			}
		}
		else
			low[x] = minn(low[x], dfn[y]);
	}
}
int main()
{
	int i, n, m, x, y, k = 0;
	n = re();
	m = re();
	for (i = 1; i <= m; i++)
	{
		x = re();
		y = re();
		add(x, y);
		add(y, x);
	}
	for (i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(r = i);
	for (i = 1; i <= n; i++)
		if (v[i])
			an[++k] = i;
	printf("%d
", k);
	for (i = 1; i <= k; i++)
		printf("%d ", an[i]);
	return 0;
}