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

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

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

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

4、60;   By Sempr - 2006.06.16*/#include <stdio.h>#include <string.h>#define G_size 100000#define V_size 11000typedef struct Graph    int id;    int next; Graph;typedef struct Edge    int s, e; Edge;Edge EG_size;Graph GAG_size, GTG_size

5、;int N, M;int G_end;int orderV_size, idV_size, visV_size, inV_size;int cnt, scnt, pos;void Insert(int s, int e) /建立原图和逆图    int p;    p = s;    while (GAp.next)        p = GAp.next;    GAG_end.id = e; 

6、;   GAp.next = G_end;    p = e;    while (GTp.next)        p = GTp.next;    GTG_end.id = s;    GTp.next = G_end;    G_end+;void DFST(int x) /对逆图进行搜索    int p, q;

7、0;   visx = 1;    p = GTx.next;    while (p)            q = GTp.id;        if (!visq)            DFST(q);  

8、60;     p = GTp.next;        ordercnt+ = x;void DFSA(int x) /对原图进行搜索    int p, q;    visx = 1;    idx = cnt;    p = GAx.next;    while (p)       

9、     q = GAp.id;        if (!visq)            DFSA(q);        p = GAp.next;    void Solve() /主要过程    int s, e;  

10、60; int i;    memset(GA, 0, sizeof(GA);    memset(GT, 0, sizeof(GT);    memset(E, 0, sizeof(E);    G_end = N + 1;    for (i = 0; i < M; i+)            scanf("%d %d&quo

11、t;, &s, &e);        Ei.s = s - 1;        Ei.e = e - 1;        Insert(s - 1, e - 1);        memset(vis, 0, sizeof(vis);    cnt = 0;  

12、  for (i = 0; i < N; i+)            if (!visi)                    DFST(i);              

13、0; memset(vis, 0, sizeof(vis);    cnt = 0;    for (i = N - 1; i >= 0; i-)            if (!visorderi)                    DFSA(or

14、deri);            cnt+;                for (i = 0; i < M; i+)            s = idEi.s;       

15、e = idEi.e;        if (s != e)                    ins+;                scnt = cnt;    cnt = 0;&

16、#160;   for (i = 0; i < scnt; i+)            if (ini = 0)                    pos = i;          &#

17、160; cnt+;                if (cnt != 1)            printf("0n");        else            cnt = 0

18、;        for (i = 0; i < N; i+)                    if (inidi = pos)                  &#

19、160;         cnt+;                            printf("%dn", cnt);    int main()    while (EOF !

20、= scanf("%d %d", &N, &M)        Solve();    return 0;Gabow算法/*    求有向图的强连通分量的Gabows algorithm    By Sempr - 2006.06.14*/#include <stdio.h>#include <algorithm>#include <stack>#define si

21、ze 11000using namespace std;int N, M;typedef struct Node    int id;    int next; Node;typedef struct Edge    int s, e;Edge;Edge Esize * 6;Node Gsize * 7;int presize, idsize;typedef stack<int> Stack;Stack S, path;int end;int cnt, scnt;int vissize;int

22、 insize;void Insert(int s, int e)    int p = s;    while (Gp.next)            p = Gp.next;        if (Gp.id = e)             

23、       return;                Gp.next = end;    Gend.id = e;    end+;void scR(int w)    int v;    int p, t;    prew = cnt+; &

24、#160;  S.push(w);    path.push(w);    p = Gw.next;    while (p)            t = Gp.id;        p = Gp.next;        if (pret = -1)

25、60;           scR(t);        else if (idt = -1)            while (prepath.top() > pret)           

26、0;    path.pop();        if (path.top() = w)        path.pop();    else        return;    do            i

27、dv = S.top() = scnt;        S.pop();        while (v != w);    scnt+;void Gabow()    int i;    memset(pre, -1, sizeof(pre);    memset(id, -1, sizeof(id);    cnt

28、 = 0;    scnt = 0;    while (!S.empty()        S.pop();    while (!path.empty()        path.pop();    for (i = 1; i <= N; i+)        

29、;    if (prei = -1)                    scR(i);            void DFS(int w, int d)    int p = Gw.next;    d+; &#

30、160;  prew = 1;    if (d > cnt)            cnt = d;        while (p)            if (preGp.id != 1)         

31、           DFS(Gp.id, d);                p = Gp.next;    void Solve()    int i, s, e;    int pos;    memset(G, 0, sizeof

32、(G);    end = N + 10;    memset(in, 0, sizeof(in);    for (i = 0; i < M; i+)            scanf("%d %d", &s, &e);        Ei.s = s;   

33、60;    Ei.e = e;        Insert(s, e);        Gabow();    memset(G, 0, sizeof(G);    memset(pre, 0, sizeof(pre);    end = scnt + 10;    for (i = 0; i < M; i+)

34、            s = idEi.s;        e = idEi.e;        if (s != e)                    ins+;                cnt = 0;    for (i = 0; i < scnt; i+)            if (ini = 0)