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

题目链接

题解

今天复习了一下割点。

关于\(tarjan\)这里不多讲

\(dfn\)和\(low\)数组的定义想必大家都知道

仔细观察一下，可以发现

假设便利\(u->v\)这条边

如果 \(low[v] >= dfn[u]\) 就说明\(v\)能到的最小时间戳的点在遍历\(u\)之后，那么\(u\)就是割点

最后特判一下\(tarjan\)第一次的点

Code

#include<bits/stdc++.h>

using namespace std;

const int N = 20010, M = 200010;

struct node {

	int to, next;

}g[M];

int last[N], gl;

inline void add(int x, int y) {

	g[++gl] = (node) {y, last[x]};

	last[x] = gl;

	return ;

}

int dfn[N], low[N], cnt, ans;

bool bj[N], vis[N];

void tarjan(int u, int f) {

	dfn[u] = low[u] = ++cnt;

	vis[u] = 1;

	int son = 0;

	for (int i = last[u]; i; i = g[i].next) {

		int v = g[i].to;

		if (!dfn[v]) {

			tarjan(v, u),low[u] = min(low[u], low[v]);

			if (!f) son++;

			else if (low[v] >= dfn[u] && !bj[u]) bj[u] = 1, ans++;

		}

		else if (vis[v]) low[u] = min(low[u], dfn[v]);

	}

	if (!f && son > 2) ans++, bj[u] = 1;

	return ;

}

int main() {

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

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

		int x, y; scanf("%d%d", &x, &y);

		add(x, y), add(y, x);

	}

	for (int i = 1; i <= n; i++)

		if (!dfn[i]) tarjan(i, 0);

	cout<<ans<<endl;

	for (int i = 1; i <= n; i++)

		if (bj[i]) printf("%d ", i);

	return 0;

}