Articles published by YorkWu

YorkWu
  1. Home
  2. YorkWu

图论——Tarjan算法求lca

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

    • 你好，初次见面。

    你好
  • YorkWu
  • March 10, 2019
  • No comments

    • Luogu P3398 仓鼠找sugar

    Luogu P3398 仓鼠找sugar
  • YorkWu
  • March 9, 2019
  • No comments

    • Luogu P3128 [USACO15DEC]最大流Max Flow

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

    • Luogu P2024 [NOI2001]食物链

    题目描述动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。 现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道 它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述： 第一种说法是“1 X Y”，表示 X 和 Y 是同类。 第二种说法是“2 X Y”，表示 X 吃 Y 。 ...
  • YorkWu
  • March 9, 2019
  • No comments

    • 清北学堂noip2019集训D5——动态规划

    动态规划
  • YorkWu
  • March 9, 2019
  • No comments

    • 清北学堂noip2019集训D2——数据结构

    基本数据结构
  • YorkWu
  • March 9, 2019
  • No comments

    • 清北学堂noip2018集训D4

    title: " 清北学堂noip2018集训D4\t\t"tags:图论url: 31.htmlid: 31categories:OI集训date: 2019-03-09 16:24:45P.S.最小生成树，最短路问题，SPFA算法，强连通分量。
  • YorkWu
  • March 9, 2019
  • No comments