社区讨论
tarjan求割点 为什么son++不能在if(!dfn[v])外
灌水区参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m3xu95jw
- 此快照首次捕获于
- 2024/11/26 10:29 去年
- 此快照最后确认于
- 2025/11/04 13:54 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,ut,vt,wt,root,dfn[100010],low[100010],cnt;
vector<int> g[100010];
bool iscut[100010];
vector<int> cut;
void tarjan(int u,int fa) {
int son = 0;
dfn[u] = low[u] = ++cnt;
for (int i = 0;i < g[u].size();i ++) {
int v = g[u][i];
if (!dfn[v]) {
++ son;
tarjan(v,u);
low[u] = min(low[u],low[v]);
if (low[v] >= dfn[u] && u != root) iscut[u] = true;//////
} else if (v != fa) low[u] = min(low[u],dfn[v]);//
}
if (u == root && son >= 2) iscut[u] = true;//////
return;
}
int main() {
scanf("%d%d",&n,&m);
for (int i = 1;i <= m;i ++) {
scanf("%d%d",&ut,&vt);
g[ut].push_back(vt);
g[vt].push_back(ut);
}
for (int i = 1;i <= n;i ++) {
// memset(dfn,0,sizeof(dfn));
// memset(low,0,sizeof(low));
root = i;
if (!dfn[i]) tarjan(i,0);
}
for (int i = 1;i <= n;i ++)
if (iscut[i]) cut.push_back(i);
printf("%d\n",cut.size());
for (int i = 0;i < cut.size();i ++)
printf("%d ",cut[i]);
printf("\n");
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...