一点建议

1
0

这一周的提示里面出现了错字。

"可能出现两种情况:..."

"第种情况,..."

"第(疑为“”)种情况,..."

而且提示的文字有不通顺、不确切之处。

“对于一个无向图的子图,当删除其中任意一个点后,不改变图内点的连通性,这样的子图叫做点的双连通子图。而当子图的边数达到最大时,叫做点的双连通分量。”没有明确,该子图是连通与否。

”第一种情况下,桥两边都各是一个连通分量,那么桥的存在把整个图分成了3个连通分量,桥本身作为一个点的双连通分量,而A,B两个分量还无法判定。在这图中,A,B两点本质都是割点。“这段话也有语义不明之处。

希望以后能对提示部分的文字多加润色,方便理解。

4 answer(s)

2

收到。我们再仔细review几遍。
大家觉得哪里写的不好,欢迎吐槽。

0

可以AC的伪代码。

void dfs(int u) {
    //记录dfs遍历次序
    static int counter = 0; 

    //记录节点u的子树数
    int children = 0;

    ArcNode *p = graph[u].firstArc;
    visit[u] = 1;

    //初始化dfn与low
    dfn[u] = low[u] = ++counter;

    for(; p != NULL; p = p->next) {
        int v = p->adjvex;
        if(edge(u,v)已经被标记) continue;                           // 修改 1

        //节点v未被访问,则(u,v)为树边
        if(!visit[v]) {
            children++;
            parent[v] = u;
            edgeStack[top++] = edge(u,v); // 将边入栈               // 修改 2
            dfs(v);

            low[u] = min(low[u], low[v]);

            //case (1)
            if(parent[u] == NIL && children > 1) {
                printf("articulation point: %d\n", u);
                // mark edge
                // 将边出栈,直到当前边出栈为止,这些边标记为同一个组
                do {
                    nowEdge = edgeStack[top];
                    top--;
                    // 标记nowEdge
                }   while (nowEdge != edge(u,v))
            }

            //case (2)
            if(parent[u] != NIL && low[v] >= dfn[u]) {
                printf("articulation point: %d\n", u);
                // mark edge
                // 将边出栈,直到当前边出栈为止,这些边标记为同一个组
                do {
                    nowEdge = edgeStack[top];
                    top--;
                    // 标记nowEdge
                }   while (nowEdge != edge(u,v))
            }

        }

        //节点v已访问,则(u,v)为回边
        else if(v != parent[u]) {
            edgeStack[top++] = edge(u,v); // 将边入栈                // 修改 3
            low[u] = min(low[u], dfn[v]);
        }
    }
}
4

可以AC的伪代码。

void dfs(int u) {
    //记录dfs遍历次序
    static int counter = 0; 

    //记录节点u的子树数
    int children = 0;

    ArcNode *p = graph[u].firstArc;
    visit[u] = 1;

    //初始化dfn与low
    dfn[u] = low[u] = ++counter;

    for(; p != NULL; p = p->next) {
        int v = p->adjvex;
        if(edge(u,v)已经被标记) continue;                           // 修改 1

        //节点v未被访问,则(u,v)为树边
        if(!visit[v]) {
            children++;
            parent[v] = u;
            edgeStack[top++] = edge(u,v); // 将边入栈               // 修改 2
            dfs(v);

            low[u] = min(low[u], low[v]);

            //case (1)
            if(parent[u] == NIL && children > 1) {
                printf("articulation point: %d\n", u);
                // mark edge
                // 将边出栈,直到当前边出栈为止,这些边标记为同一个组
                do {
                    nowEdge = edgeStack[top];
                    top--;
                    // 标记nowEdge
                }   while (nowEdge != edge(u,v))
            }

            //case (2)
            if(parent[u] != NIL && low[v] >= dfn[u]) {
                printf("articulation point: %d\n", u);
                // mark edge
                // 将边出栈,直到当前边出栈为止,这些边标记为同一个组
                do {
                    nowEdge = edgeStack[top];
                    top--;
                    // 标记nowEdge
                }   while (nowEdge != edge(u,v))
            }

        }

        //节点v已访问,则(u,v)为回边
        else if(v != parent[u]) {
            edgeStack[top++] = edge(u,v); // 将边入栈                // 修改 3
            low[u] = min(low[u], dfn[v]);
        }
    }
}
  • 参考这段伪代码写了程序,提交只有90分,不知遗漏了什么情况……求测试样例求点拨

  • 这段伪代码也是错的,『提示』里的讲解有问题,建议你看Taryan的论文。 https://dx.doi.org/10.1137%2F0201010

  • 这篇代码没问题,亲测AC

  • 我觉得伪代码有问题,4个点,4条边,边(1,2),(2,3),(2,4),(3,4),1是根,如果从1开始dfs,貌似(1,2)这条表不会被标记。那个走火的代码我看了,他使用伪代码后,他自己在后面加了个自己写的一个函数避免了这点。然而这明明就是伪代码少写了什么,伪代码有错!

  • 添加评论
  • reply
0

这个题在说什么

write answer 切换为英文 切换为中文


转发分享