快速选择算法,是一种能在大致O(N)的时间内选取数组中第k大或者k小的算法.其基本思路与快速排序算法类似,也是分治的思想.
其实这个算法是个基础算法,但是不常用,所以今天编的时候错了POJ2388,才有了这篇文章.
- 执行Partition算法(就是那个快排里将区间内所有数划分为小的一部分和大的一部分的过程)
- 判断第k大的数是在小的部分还是大的部分
- 递归,直到区间足够小,返回结果
标签： 算法
处理SCC(强连通分量问题)的Tarjan算法
在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected),如果有向图G的每两个顶点都强连通，称G是一个强连通图.
通俗的说法是:从图G内任意一个点出发,存在通向图G内任意一点的的一条路径.
非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components,SCC).
求图强连通分量的意义是:由于强连通分量内部的节点性质相同,可以将一个强连通分量内的节点缩成一个点,即消除了环,这样,原图就变成了一个有向无环图(directed acyclic graph,DAG).显然对于一个无向图,求强连通分量没有什么意义,联通即为强连通.
求强连通分量比较高效的算法是SCC Tarjan算法,BYV牛有一个很好的说明,推荐大家看一看:有向图强连通分量的Tarjan算法« Beyond the Void,我在这里就不照搬了.
Tarjan 算法基本基于DFS,时间复杂度就是遍历图一遍,为\(\Theta (N)\),Tarjan 貌似很喜欢深搜的样子,LCA被深搜活生生的弄成了\(\Theta (N)\),SCC 看来一样,Tarjan 一出现,时间复杂度果然降了一个数量级.
先看BYV牛的CODE,写的真不错,虽然第一遍我没看懂,不过相信加了注释后会好理解多,如果有错误,别打我.
Continue reading “处理SCC(强连通分量问题)的Tarjan算法”
用于求最近公共祖先(LCA)的 Tarjan算法–以POJ1986为例
LCA_Tarjan最近公共祖先问题LCA(Least Common Ancestors)问题是这样一个问题
给定有向无环图(就是树,不一定有没有根),给定点U,V,找出点R,保证点R是U,V的公共祖先,且深度最深;或者理解为R离这两个点的距离之和最小.如何找出R呢？
最一般的算法是DFS(DFS本是深度优先搜索,在这里姑且把深度优先遍历也叫做DFS,其实是一种不严谨的说法).先看一道赤裸裸的LCA:POJ 1330 Nearest Common Ancestors 这道题给出了根节点,还保证”the first integer is the parent node of the second integer”(输入第一个数是第二个数的祖先),这是赤裸裸的LCA,算法很简单,从根节点DFS一遍,按DFS层数k给每个节点标上深度deep[i]=k.然后从U点DFS到V点,找到后回溯,在回溯的路径上找到一个deep[i]最小的节点即为LCA.
强大的LCA Tarjan算法能在一遍遍历后应答全部的LCA查询,时间复杂的约为\(\Theta (N)\)
有人说POJ1330是一道LCA Tarjan,在我看来完全不是,LCA Tarjan算法的用途是处理大量请求,如果只有几个(POJ1330每个Case只有一个)询问大可不必写Tarjan算法,不过,1986的编程难度高,如果只是想先学LCA Tarjan, 用1330验证正确性也不是不可以.
LCA Tarjan算法
再来看一道题:POJ1986 Distance Queries 这道题才是真正的LCA Tarjan,只给一个有向无环图,有海量询问;(注意,输入格式与POJ 1984 Navigation Nightmare 一样,需要参考1984的输入格式)
输入格式大意:
- 第1行：节点数N,边数M
- 第2…M+1行：起始节点,目标节点,路径长度,方向(无意义字符,本题直接忽略)
- 第M+2行:询问个数K(1 <= K <= 10,000)
- 第N+3…2+M+K行:查询 U,V
这道题用DFS做的时间复杂度为\(\Theta (K \times N) \) 显然很不理想,这个时候伟大的Tarjan来了,问题迎刃而解.
首先,LCA Tarjan 是一种离线算法,要求一次读入所有询问,一次性输出,这正是LCA Tarjan 算法的精髓
以下大量引用Sideman神牛的话：
LCA Tarjan基本框架：
- 先用随便一种数据结构(链表就行),把关于某个点的所有询问标在节点上,保证遍历到一个点,能得到所有有关这个节点LCA 查询
- 建立并查集.注意:这个并查集只可以把叶子节点并到根节点,即getf(x)得到的总是x的祖先
- 深度优先遍历整棵树,用一个Visited数组标记遍历过的节点,每遍历到一个节点将Visite[i]设成True 处理关于这个节点(不妨设为A)的询问,若另一节点(设为B)的Visited[B]==True,则回应这个询问,这个询问的结果就是getf(B). 否则什么都不做
- 当A所有子树都已经遍历过之后,将这个节点用并查集并到他的父节点(其实这一步应该说当叶子节点回溯回来之后将叶子节点并到自己,并DFS另一子树)
- 当一颗子树遍历完时,这棵子树的内部查询(即LCA在这棵子树内部)都已经处理了