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

典型算法与ACM题目解析(02)有向图的强连通分量上一篇:典型算法与ACM题目解析(01)寻找最大流的标号法下一篇:关于STL中优先队列的用法作者:dzf阅读次数:87时间:2006-11-27 21:23:49算法园地这道题是POJ的2186题，题意是说，有一群牛，总数为N(N2,2=3,3=1，所以这解这道题最好的方法是使用有向图的强连通分量。在同一个强连通分量里的所有的牛之间是互相仰慕的，我们将其缩为一点，并且只记录这一点的牛的数量，如果有最受欢迎的牛存在，那么这个图将是连通图，并且出度为零的点只有一个，我们可以用并查集来判是否连通，然后计算每个节点的出度，即可求出最受欢迎的牛的数量。求强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法，其中Kosaraju算法要对原图和逆图都进行一次DFS，而另外两种算法只要DFS一次就可以了用了Gabow算法和Kosaraju算法各写了一遍在时间上Gabow算法是122ms,Kosaraju算法是61ms理论上Gabow算法要比Kosaraju快些的，因为Gabow算法只对原图进行一次DFS而Kosaraju要进行两次Gabow反而慢的原因可能是我用了STL里的stackPS:我没看懂Gabow算法，完全是对着书上写的代码如下:Kosaraju算法/* 求有向图的强连通分量的Kosarajus algorithm By Sempr - 2006.06.16*/#include #include #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;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; 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; visx = 1; p = GTx.next; while (p) q = GTp.id; if (!visq) DFST(q); p = GTp.next; ordercnt+ = x;void DFSA(int x) /对原图进行搜索 int p, q; visx = 1; idx = cnt; p = GAx.next; while (p) q = GAp.id; if (!visq) DFSA(q); p = GAp.next; void Solve() /主要过程 int s, e; 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, &s, &e); Ei.s = s - 1; Ei.e = e - 1; Insert(s - 1, e - 1); memset(vis, 0, sizeof(vis); cnt = 0; for (i = 0; i = 0; i-) if (!visorderi) DFSA(orderi); cnt+; for (i = 0; i M; i+) s = idEi.s; e = idEi.e; if (s != e) ins+; scnt = cnt; cnt = 0; for (i = 0; i scnt; i+) if (ini = 0) pos = i; cnt+; if (cnt != 1) printf(0n); else cnt = 0; for (i = 0; i N; i+) if (inidi = pos) cnt+; printf(%dn, cnt); int main() while (EOF != scanf(%d %d, &N, &M) Solve(); return 0;Gabow算法/* 求有向图的强连通分量的Gabows algorithm By Sempr - 2006.06.14*/#include #include #include #define size 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 Stack;Stack S, path;int end;int cnt, scnt;int vissize;int insize;void Insert(int s, int e) int p = s; while (Gp.next) p = Gp.next; if (Gp.id = e) return; Gp.next = end; Gend.id = e; end+;void scR(int w) int v; int p, t; prew = cnt+; S.push(w); path.push(w); p = Gw.next; while (p) t = Gp.id; p = Gp.next; if (pret = -1) scR(t); else if (idt = -1) while (prepath.top() pret) path.pop(); if (path.top() = w) path.pop(); else return; do idv = S.top() = scnt; S.pop(); while (v != w); scnt+;void Gabow() int i; memset(pre, -1, sizeof(pre); memset(id, -1, sizeof(id); cnt = 0; scnt = 0; while (!S.empty() S.pop(); while (!path.empty() path.pop(); for (i = 1; i cnt) cnt = d; while (p) if (preGp.id != 1) DFS(Gp.id, d); p = Gp.next; void Solve() int i, s, e; int pos; memset(G, 0, sizeof(G); end = N + 10; memset(in, 0, sizeof(in); for (i = 0; i M; i+) scanf(%d %d, &s, &e); Ei.s = s; 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+) s = idEi.s; e = idEi.e; if (s != e) ins+; cnt = 0; for (i = 0; i scnt; i+) if (ini = 0) pos = i;