Articles published by YorkWu

YorkWu
  1. Home
  2. YorkWu

无向图的双连通分量

双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点(一条边)都不会改变此图的连通性，即不存在割点(桥)，则称作点(边)双连通图。一个无向图中的每一个极大点(边)双连通子图称作此无向图的点(边)双连通分量。——来自360百科
  • YorkWu
  • March 13, 2019
  • No comments

    • Luogu P3469 [POI2008]BLO-Blockade

    题目链接
  • YorkWu
  • March 12, 2019
  • No comments

    • Tarjan求割点

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

    • Tarjan求割边、桥

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

    • Luogu P1353 [USACO08JAN]跑步Running

    题目链接
  • YorkWu
  • March 12, 2019
  • No comments

    • Luogu P2327 [SCOI2005]扫雷

    题目链接
  • YorkWu
  • March 11, 2019
  • No comments

    • P2331 [SCOI2005]最大子矩阵

    P2331 [SCOI2005]最大子矩阵
  • YorkWu
  • March 11, 2019
  • No comments

    • 图论——Tarjan算法求lca

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