标签:tarjan

tarjan【桥、割点、点双、边双、支配树】 Summary

huangkui 2018年2月27日 No Comments Algorithm, Problem, Summary , , , , ,

知识点总结 定义 割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点。 割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。 点连通度:最小割点集合中的顶点数。

LCA总结

huangkui 2017年8月8日 1 Comment Algorithm, 未分类 , , , , , ,

这段时间一直在学习LCA的各种算法,下面就对LCA的各种算法进行一次总结: 问题概述 LCA(最近公共祖先)指的是在一棵树上两个节点的最近的公共祖先(这句话好像跟没说差不多),也就是深度最深的公共祖先。LCA的适用范围非常广,在许多较难的与树有关的题中都会需要用到。因此,掌握求LCA的方法是非常重要的。

Page 1 of 1