社区讨论

哪个写法更好??

灌水区参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@m3sedwln
此快照首次捕获于
2024/11/22 15:06
去年
此快照最后确认于
2025/11/04 14:12
4 个月前
查看原帖
tarjan求割点如下两写法
1
CPP
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
CPP
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 条回复,欢迎继续交流。

正在加载回复...