O(E + V) to find articulation points of a graph in Scala (based on http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html)

gistfile1.scala

/** *
    * This function assumes that the graph is a single connected graph
    * @param graph adjencency list (node id's must be zero based)
    * @return The nodes that are the articulation points
    */
  def articulationPoints(graph: Array[mutable.BitSet]): BitSet = {
    val result = new mutable.BitSet()
    val depth = Array.fill[Int](graph.length)(-1)
    val lowest = Array.fill[Int](graph.length)(-1)
    var count = 0
    def depthFirstSearch(parent: Int, currentVertex: Int) {
      var children = 0
      depth(currentVertex) = count
      lowest(currentVertex) = count
      count += 1
      graph(currentVertex).foreach { neighbor =>
        // if unvisited
        if (depth(neighbor) == -1) {
          children += 1
          depthFirstSearch(currentVertex, neighbor)

          lowest(currentVertex) = Math.min(lowest(currentVertex), lowest(neighbor))

          if (lowest(neighbor) >= depth(currentVertex) && currentVertex != parent)
            result += currentVertex
        }
        // update low number - ignore parent (that's where we came from)
        else if (neighbor != parent)
          lowest(currentVertex) = Math.min(lowest(currentVertex), depth(neighbor))
      }
      if (currentVertex == parent && children > 1)
        result += currentVertex
    }
    depthFirstSearch(0, 0)
    result
  }
}