社区讨论
哪个写法更好??
灌水区参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m3sedwln
- 此快照首次捕获于
- 2024/11/22 15:06 去年
- 此快照最后确认于
- 2025/11/04 14:12 4 个月前
tarjan求割点如下两写法
1
CPP1
void cutp(int u, int fa){
dfn[u] = low[u] = ++num;
int child = 0;
for(int i = head[u];i;i = edge[i].nxt) {
int v = edge[i].v;
if(!dfn[v]) {
child++;
cutp(v, u);
low[u] = min(low[u], low[v]);
if((u == fa && child > 1) || (u != fa && low[v] >= dfn[u]))
iscut[u] = 1;
}
else low[u] = min(low[u], dfn[v]);
}
}
2
void dfs(int u, int fa) {
low[u] = num[u] = ++dfn;
int child = 0;
for(int i =head[u]; i ; i = edge[i].nxt) {
int v = edge[i].v;
if(!num[v]) {
if(u == fa) child++;
dfs(v, u);
low[u] = min(low[v], low[u]);
if(low[v] >= num[u] && u != fa) {
iscut[u] =1;
}
}
else if(num[v] < num[u] && v != fa)
low[u] = min(low[u], num[v]);
}
if( u == fa && child >= 2) {
iscut[fa] = 1;
}
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...