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

先给链接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:如果图非连通,那么,至少存在两个独立的连通分量,问题一定无解。

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

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

本人的代码很丑,用的前向星,第一次写前向星,被yxc同志指为”光建图排序就要\(N\log (N)\)“所以用的计数排序,建图部分是为了前向星而前向星,直接无视即可

MY CODE:

再说POJ 1236 Network of Schools

题意及解法(转自极限定律),写的很好

题目大意:N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后,可以通过单向网络向周边的学校传输,问题1:初始至少需要向多少个学校发放软件,使得网络内所有的学校最终都能得到软件.2,至少需要添加几条传输线路(边),使任意向一个学校发放软件后,经过若干次传送,网络内所有的学校最终都能得到软件。

具体算法:先用Korasaju Algorithm求出有向图所有的强连通分量(当然Comzyh是用的Tarjan),然后将所有的强连通分量缩成一个点(缩点),这样原来的有向图就缩成了一个DAG图(有向无环图);用2个数组分别记录新生成的DAG图中的每个顶点(包括原来的顶点和强连通分量的缩点)是否有出边和入边,最后遍历每个顶点,如果没有入边,则ans1++;如果没有出边,ans2++.最后所求即为ans1和max(ans1,ans2).

注意如果最终仅有一个强连通分量,显然第二问应输出0而不是1
这道题的代码比上一题简洁的多了
MY CODE:

原创文章,转载请注明: 转载自Comzyh的博客

本文链接地址: POJ 2186 & 1236 强连通分量 Tarjan算法

4 replies on “POJ 2186 & 1236 强连通分量 Tarjan算法

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据