典型算法与acm题目解析(02)—有向图的强连通分量

《典型算法与acm题目解析(02)—有向图的强连通分量》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、典型算法与ACM题目解析(02)—有向图的强连通分量上一篇:典型算法与ACM题目解析(01)—寻找最大流的标号法   下一篇:关于STL中优先队列的用法作者:dzf   阅读次数:87   时间:2006-11-2721:23:49   算法园地这道题是POJ的2186题，题意是说，有一群牛，总数为N(N<=10000),题目数据给出牛之间的关系，比如说1仰慕2，2仰慕3等等，设这种仰慕是可以传递的，如果1仰慕2，那么1也会同时仰慕2仰慕的那些牛，如果一头牛被所有的牛都仰慕，那么它将是最受欢迎的牛，题目要求的是有多少牛是"最受欢迎的"。这道题目大家第一眼看到可

2、能感觉直接模拟，但是由于数据量巨大，模拟的话肯定是过不了的，而且题目中还会出现环路的情况，比如1=>2,2=>3,3=>1，所以这解这道题最好的方法是使用有向图的强连通分量。在同一个强连通分量里的所有的牛之间是互相仰慕的，我们将其缩为一点，并且只记录这一点的牛的数量，如果有最受欢迎的牛存在，那么这个图将是连通图，并且出度为零的点只有一个，我们可以用并查集来判是否连通，然后计算每个节点的出度，即可求出最受欢迎的牛的数量。求强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法，其中Kosaraju算法要对原图和逆图都进行一次DFS，而

3、另外两种算法只要DFS一次就可以了用了Gabow算法和Kosaraju算法各写了一遍在时间上Gabow算法是122ms,Kosaraju算法是61ms理论上Gabow算法要比Kosaraju快些的，因为Gabow算法只对原图进行一次DFS而Kosaraju要进行两次Gabow反而慢的原因可能是我用了STL里的stackPS:我没看懂Gabow算法，完全是对着书上写的代码如下:Kosaraju算法/*   求有向图的强连通分量的Kosaraju‘salgorithm   BySempr----2006.06.16*/#include#inclu

4、de#defineG_size100000#defineV_size11000typedefstructGraph{   intid;   intnext;}Graph;typedefstructEdge{   ints,e;}Edge;EdgeE[G_size];GraphGA[G_size],GT[G_size];intN,M;intG_end;intorder[V_size],id[V_size],vis[V_size],in[V_size];intcnt,scnt,pos;voidInsert(ints,inte)//建立原图和逆图

5、{   intp;   p=s;   while(GA[p].next)       p=GA[p].next;   GA[G_end].id=e;   GA[p].next=G_end;   p=e;   while(GT[p].next)       p=GT[p].next;   GT[G_end].id=s;   GT[p].next=G_end;   G_end++;}voidDFST(intx)//对逆图进行搜索{   intp,q;   vis[x]=1;   p=GT[x].next;   while(p)   {       q=GT[p].

6、id;       if(!vis[q])           DFST(q);       p=GT[p].next;   }   order[cnt++]=x;}voidDFSA(intx)//对原图进行搜索{   intp,q;   vis[x]=1;   id[x]=cnt;   p=GA[x].next;   while(p)   {       q=GA[p].id;       if(!vis[q])           DFSA(q);       p=GA[p].next;   }}voidSolve()//主要过程{   ints,e;  

7、 inti;   memset(GA,0,sizeof(GA));   memset(GT,0,sizeof(GT));   memset(E,0,sizeof(E));   G_end=N+1;   for(i=0;i

8、vis[i])       {