社区讨论
模板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 条回复,欢迎继续交流。
正在加载回复...