社区讨论

模板0分求助

P3388【模板】割点(割顶)参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi7yq20o
此快照首次捕获于
2025/11/21 05:47
4 个月前
此快照最后确认于
2025/11/21 05:47
4 个月前
查看原帖
CPP
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 20001;
int n, m;
vector<int> G[MAXN];
int dfn[MAXN], low[MAXN], k;
bool isc[MAXN];
inline void init() {
	memset(G, 0, sizeof G);
	memset(dfn, 0, sizeof dfn); memset(low, 0, sizeof low); k = 0;
	memset(isc, 0, sizeof isc);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		G[u].push_back(v); G[v].push_back(u);
	}
}

#define Min(a, b) ( a < b ? a : b )
inline void Tarjan(int x, int f) {
	dfn[x] = low[x] = ++k;
	int child = 0;
	for(int i = 0; i < int(G[x].size()); i++) {
		int v = G[x][i];
		if(!dfn[v]) {
			child++;
			Tarjan(v, x);
			if(low[v] >= dfn[x]) 
				isc[x] = 1;
			low[x] = Min(low[x], low[v]);
		}
		else if(dfn[x] > dfn[v] && v != f)
			low[x] = Min(low[x], dfn[v]);
	}
	if(f == -1 && child < 2) isc[x] = 0;
}

int main() {
	init();
	for(int i = 1; i <= n; i++)
		if(!dfn[i])
			Tarjan(1, -1);
	for(int i = 1; i <= n; i++)
		if(isc[i])
			printf("%d\n", i);
}

回复

3 条回复,欢迎继续交流。

正在加载回复...