Articles in the category of 类目

  1. Home
  2. 类目

Tarjan求割点

Tarjan求割点
  • YorkWu
  • March 12, 2019
  • No comments

    • Tarjan求割边、桥

    Tarjan求割点、桥
  • YorkWu
  • March 12, 2019
  • No comments

    • 图论——Tarjan算法求lca

    tarjan算法本质是使用并查集对“向上标记法”的一种优化。它是一个离线算法。理论时间复杂度为$O(n+m)$。在dfs当中，树中的节点一共可以分为3类：已经访问完毕并且回溯的节点。在这些节点标记2。已经开始递归，但是尚未回溯的节点。这些节点就是当前正在访问的节点$x$以及$x$的祖先。在这些节点标记1。尚未访问的节点。不标记。对于正在访问的节点$x$，它到根节点的路径以及标记为1。若$y$...
  • YorkWu
  • March 11, 2019
  • No comments