关于寻找割点

Question

波波老师，割点那一节好像发现有个小bug，如果是这种情形好像无法找到割点2，不知道我理解有没有错：
5，6
0，1
0，2
1，2
2，3
2，4
3，4

Answer 1

liuyubobobo 2020-03-17 13:15:10

赞！确实有 bug。

dfs 里 for 循环中，else if 一部分应该是：

else if(w != parent)
    low[v] = Math.min(low[v], ord[w]);

感谢提醒，我找时间做一个勘误！

抱歉！要是愿意可以加我的微信，我会给你发一个小红包：）liuyubobobo

继续加油！：）

• 提问者 zengxing358 #1

  嗯嗯，好的。谢谢波波老师

• Schwarzeni #2

  老师您好，我还是按照 `low[v] = Math.min(low[v], low[w])` 这样的逻辑，但是我写了两个循环：
  - 第一个循环里就是 DFS 
  - 第二个循环里才是用来修改 low 数组以及判断是否为割点
  这样写是没有 bug 的
  ```go
  dfs = func(parentNode int, currentNode int, order int) {
    ord[currentNode] = order
    low[currentNode] = order
    visited[currentNode] = true
  
    childCount := 0
    for _, v := range g.Adj(currentNode) {
      if !visited[v] {
        order += 1
        dfs(currentNode, v, order)
        childCount += 1
      }
    }
  
    // 处理根节点的情况
    if startNode == currentNode {
      if childCount > 1 {
        result = append(result, currentNode)
      }
      return
    }
  
    for _, v := range g.Adj(currentNode) {
      if v != parentNode {
        if low[v] < low[currentNode] {
          low[currentNode] = low[v]
        } else if low[v] >= ord[currentNode] {
          result = append(result, currentNode)
          break
        }
      }
    }
  }
  ```