comzyh | Comzyh的博客

明天该NOIP了,在宾馆写Blog别有一番风味,以后或许就不能更新Blog了,这种失落简直是难熬的
求\(RP++\\RP=100^{100^{100}}\)
如果时间 OI之路就此中止,还是有些遗憾的.据说下个月父母把网断了,希望本文不会是绝唱.这段真的很带劲,很带劲,就目前看来,继续OI的唯一途径很渺茫—省队,再议吧.
希望Comzyh留下的些许文章对你有帮助.

感谢诸位神牛们:applepi(billdu),sideman,whd,gczsjdy1994 etc.

迄今为止,
来访者562
访问数1888 很吉利吧
没办法,小博客

Can I help you ??

POJ 2186 & 1236 强连通分量 Tarjan算法

Posted on 2010年11月12日2014年07月28日 by comzyh

先给链接POJ 2186 Popular Cows ,POJ 1236 Network of Schools
这两道题都是经典的强连通分量问题,本人都采用了伟大的SCC Tarjan算法.
关于SCC Tarjan算法可以参见本博的处理SCC(强连通分量问题)的Tarjan算法

先说POJ 2186 Popular Cows

(不看这题,直接跳到1236的题解)
题意:每个Cow都梦想成为牛群里最知名的奶牛,在一个有N(1 <= N <= 10,000) 头牛的牛群里,给出最多M(1 <= M <= 50,000) 个数对(A,B)告诉你A认为B是有名的,并且名气可以传递,若果A认为B有名,B认为C有名,则A也会认为C有名,即使在输入的数对中没有给出这段关系,你的任务是计算出被所有牛认为是有名的牛的个数.

引用另一位仁兄Headacher的题解中的一部分(参见PKU POJ 2186 Popular Cows 强连通分量 ),讲的很好,很精辟

算法证明：

1：假设a和b都是最受欢迎的cow，那么，a欢迎b，而且b欢迎a，于是，a和b是属于同一个连通分量内的点，所有，问题的解集构成一个强连通分量。

2：如果某个强连通分量内的点a到强连通分量外的点b有通路，因为b和a不是同一个强连通分量内的点，所以b到a一定没有通路，那么a不被b欢迎，于是a所在的连通分量一定不是解集的那个连通分量。

3：如果存在两个独立的强连通分量a和b，那么a内的点和b内的点一定不能互相到达，那么，无论是a还是b都不是解集的那个连通分量，问题保证无解。

4：如果图非连通，那么，至少存在两个独立的连通分量，问题一定无解。

这样我们便的得到了初步的解决方案

用Tarjan算法求出强连通分量,设立Belong数组,用并查集将在同一强连通分量的节点并在一起.
建树,遍历所有输入中的点对(A,B)如果AB分属两个不同的强连通分量,则belong[B]是belong[A]的父节点
显然,如果点对(A,B),A所在的强连通分量(用并查集指定,getf(A))指向的元素和”A指向的强连通分量“不属于同一强连通分量,则不构成树结构,无解.
遍历所有强连通分量,如果存在一个强连通分量指向自己,则它是最著名的强连通分量
遍历所有节点,如果属于答案强连通分量,计数器累加,最后输出答案

本人的代码很丑,用的前向星,第一次写前向星,被yxc同志指为”光建图排序就要\(N\log (N)\)“所以用的计数排序,建图部分是为了前向星而前向星,直接无视即可
Continue reading “POJ 2186 & 1236 强连通分量 Tarjan算法”

处理SCC(强连通分量问题)的Tarjan算法

Posted on 2010年11月9日2015年10月24日 by comzyh

在有向图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为例

Posted on 2010年10月25日2015年10月24日 by comzyh

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在这棵子树内部)都已经处理了

Continue reading “用于求最近公共祖先(LCA)的 Tarjan算法–以POJ1986为例”

在一维数组中以完全二叉树方式存储线段树的空间分析

Posted on 2010年10月24日2015年10月24日 by comzyh

我们大家存储线段树的方式无非两种：

二叉链表
一维数组完全二叉树

二叉链表优点是节省空间,缺点是编程复杂度大,执行效率较低,空间复杂度为2N

在一维数组以完全二叉树方式存储线段树的编程复杂度小,执行效率较高,但浪费空间
长期以来,我和我校的OIer一直不知以一维方式存储线段树到底需要开多大的数组.今天正好有些闲暇的时间,写了个小程序,分析了下一维线段树在一维方式存储下到底需要占用多少空间.经本文所述方式计算约为4N

Continue reading “在一维数组中以完全二叉树方式存储线段树的空间分析”

POJ 2777 Count Color 线段树染色

Posted on 2010年10月21日2015年10月24日 by comzyh

早些日子为了学习线段树,在Du神牛的带领下,做了此题,入门好题也! poj2777 Count Color

此题是本人线段树第二题,前一道是TYVJ1039 忠诚2(一道动态RMQ问题)

输入区间长度L (1 <= L <= 100000),颜色数目 T (1 <= T <= 30) 和指令数O (1 <= O <= 100000)

接下来O行C x y z 代表将[x,y]区间染成z色,P x y z 代表询问[x,y]有多少种颜色,起始各处颜色为1;

我第一眼看到”1 <= T <= 30″就格外激动为啥不是40呢？显然是为了小于32,所以显然可以用二进制每位表达一种颜色,颜色1是1(0x1)颜色10就是1024(0x400),在线段树里查询便可以获得这一段的几种颜色然后做一次OR操作便可得到所有颜色

我看到T的范围就马上想到到了Matrix67牛的一个位运算优化：位运算简介及实用技巧（二）：进阶篇(1) 中计算二进制中的1的个数的方法
Continue reading “POJ 2777 Count Color 线段树染色”