Mai Icy

“2024 年 5 月”

ACM程序课算法笔记17——树链剖分

ACM程序课算法笔记17——树链剖分 定义 将一个树分割成若干条链即树链剖分。 树链剖分有多种形式,有重链剖分和长链剖分。至于如何剖分,实际上就是让每个点都选择一条边,并且这些边形成多个链条,重...

ACM程序课算法笔记16——2-SAT

ACM程序课算法笔记16——2-SAT 定义 SAT 是适定性(Satisfiability)问题的简称。一般形式为 k - 适定性问题,简称 k-SAT。 对于n个集合,每个集合仅有两个元素。...

ACM程序课算法笔记15——强联通分量

ACM程序课算法笔记15——强联通分量 问题与目的 强联通的点是指,A点能到达B点,且B点能到达A点。 对于一个图,问有多少强联通分量? Kosaraju 算法 获取目标图G1的反图G2(所有边...