P3388 割点模板tle
  • 板块题目总版
  • 楼主Co27Ti22
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/12/18 00:04
  • 上次更新2023/11/5 06:00:35
查看原帖
P3388 割点模板tle
434157
Co27Ti22楼主2020/12/18 00:04
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20000, maxm = 100000;

int cut[maxn];
int low[maxn], dfn[maxn], vis[maxn];
int head[maxn];
struct node {
	int to, next;
}t[200000];

int dep;
int n, m;
int tot, cnt;

void add(int u, int v)
{
	t[++cnt].to = v;
	t[cnt].next = head[u];
	head[u] = cnt;
}

void tarjan(int u, int father)
{
	vis[u] = 1;
	dfn[u] = low[u] = ++dep;
	int child = 0;
	for (int i = head[u]; i != -1; i = t[i].next) {
		int v = t[i].to;
		// 
		if (v != father && vis[v] == 1) {
			low[u] = min(dfn[v], low[u]);
		}
		if (vis[v] == 0) {
			tarjan(v, u);
			child++;
			low[u] = min(low[u], low[v]);
			if ((father == -1 && child > 1) || (father != -1 && low[v] >= dfn[u])) {
				cut[u] = true;
			}

		}

	}
	vis[u] = 2;
}

int main()
{
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
		add(b, a);
	}
	for (int i = 1; i <= n; i++) {
		if (dfn[i] == 0) {
			tarjan(i, -1);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (cut[i]) {
			tot++;
		}
	}
	printf("%d\n", tot);
	for (int i = 1; i <= n; i++) {
		if (cut[i]) {
			printf("%d ", i);
		}
	}

	return 0;
}
2020/12/18 00:04
加载中...