图论

图论 图论算法一般都是揉在一起的,很难单独把算法拆开讲,所以直接上题目吧。分类是大致分的,其实有很多是交叉的。 二叉树 二叉树的遍历有三种,分别为前序遍历,
0001-01-01
5分钟阅读时长
LCA: Lowest common ancestor最近公共祖先 倍增求LCA 预处理向上跳2^k步的结果f[k][x] $O(n \log n)$ 求的时候先把两个点跳到一个深度,这里有一个特判,如果重合直
0001-01-01
1分钟阅读时长
前置概念 时间戳:搜索时第几个搜索到这个点。如搜索顺序是1->2->3->6,则6的时间戳为4 对于无向图 连通分量:对于图G来的一个子图
0001-01-01
3分钟阅读时长
DFS 众所周知,搜索和DP是不分家的,几乎所有的DP都可以转化为搜索。当想不出正解时,DFS也是骗分的好手段。 主要的搜索手段有: DFS/BFS爆搜 双向BF
0001-01-01
4分钟阅读时长