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

古城微笑少年丶 2022-09-19 12:25 126阅读 0赞

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

这道题是POJ的2186题，题意是说，有一群牛，总数为N(N<=10000),题目数据给出牛之间的关系，比如说1仰慕2，2仰慕3等等，设这种仰慕是可以传递的，如果1仰慕2，那么1也会同时仰慕2仰慕的那些牛，如果一头牛被所有的牛都仰慕，那么它将是最受欢迎的牛，题目要求的是有多少牛是"最受欢迎的"。

这道题目大家第一眼看到可能感觉直接模拟，但是由于数据量巨大，模拟的话肯定是过不了的，而且题目中还会出现环路的情况，比如1=>2,2=>3,3=>1，所以这解这道题最好的方法是使用有向图的强连通分量。

在同一个强连通分量里的所有的牛之间是互相仰慕的，我们将其缩为一点，并且只记录这一点的牛的数量，如果有最受欢迎的牛存在，那么这个图将是连通图，并且出度为零的点只有一个，我们可以用并查集来判是否连通，然后计算每个节点的出度，即可求出最受欢迎的牛的数量。

求强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法，其中Kosaraju算法要对原图和逆图都进行一次DFS，而另外两种算法只要DFS一次就可以了。

用了Gabow算法和Kosaraju算法各写了一遍。

在时间上Gabow算法是122ms,Kosaraju算法是61ms

理论上Gabow算法要比Kosaraju快些的，因为Gabow算法只对原图进行一次DFS，而Kosaraju要进行两次

Gabow反而慢的原因可能是我用了STL里的stack

PS:我没看懂Gabow算法，完全是对着书上写的

代码如下:

Kosaraju算法

/\*

求有向图的强连通分量的Kosaraju's algorithm

By Sempr ---- 2006.06.16

\*/

\#include <stdio.h>

\#include <string.h>

\#define G\_size 100000

\#define V\_size 11000

typedef struct Graph

int id;

int next;

\} Graph;

typedef struct Edge

int s, e;

\} Edge;

Edge E\[G\_size\];

Graph GA\[G\_size\], GT\[G\_size\];

int N, M;

int G\_end;

int order\[V\_size\], id\[V\_size\], vis\[V\_size\], in\[V\_size\];

int cnt, scnt, pos;

void Insert(int s, int e) //建立原图和逆图

int p;

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++;

void DFST(int x) //对逆图进行搜索

int p, q;

vis\[x\] = 1;

p = GT\[x\].next;

while (p)

q = GT\[p\].id;

if (!vis\[q\])

DFST(q);

p = GT\[p\].next;

order\[cnt++\] = x;

void DFSA(int x) //对原图进行搜索

int p, 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;

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);

E\[i\].s = s - 1;

E\[i\].e = e - 1;

Insert(s - 1, e - 1);

memset(vis, 0, sizeof(vis));

cnt = 0;

for (i = 0; i < N; i++)

if (!vis\[i\])

DFST(i);

memset(vis, 0, sizeof(vis));

cnt = 0;

for (i = N - 1; i >= 0; i--)

if (!vis\[order\[i\]\])

DFSA(order\[i\]);

cnt++;

for (i = 0; i < M; i++)

s = id\[E\[i\].s\];

e = id\[E\[i\].e\];

if (s != e)

in\[s\]++;

scnt = cnt;

cnt = 0;

for (i = 0; i < scnt; i++)

if (in\[i\] == 0)

pos = i;

cnt++;

if (cnt != 1)

printf("0/n");

else

cnt = 0;

for (i = 0; i < N; i++)

if (in\[id\[i\]\] == pos)

cnt++;

printf("%d/n", cnt);

int main()

while (EOF != scanf("%d %d", &N, &M))

Solve();

return 0;

Gabow算法

/\*

求有向图的强连通分量的Gabow's algorithm

By Sempr ---- 2006.06.14

\*/

\#include <stdio.h>

\#include <algorithm>

\#include <stack>

\#define size 11000

using namespace std;

int N, M;

typedef struct Node

int id;

int next;

\} Node;

typedef struct Edge

int s, e;

\}Edge;

Edge E\[size \* 6\];

Node G\[size \* 7\];

int pre\[size\], id\[size\];

typedef stack<int> Stack;

Stack S, path;

int end;

int cnt, scnt;

int vis\[size\];

int in\[size\];

void Insert(int s, int e)

int p = s;

while (G\[p\].next)

p = G\[p\].next;

if (G\[p\].id == e)

return;

G\[p\].next = end;

G\[end\].id = e;

end++;

void scR(int w)

int v;

int p, t;

pre\[w\] = cnt++;

S.push(w);

path.push(w);

p = G\[w\].next;

while (p)

t = G\[p\].id;

p = G\[p\].next;

if (pre\[t\] == -1)

scR(t);

else if (id\[t\] == -1)

while (pre\[path.top()\] > pre\[t\])

path.pop();

if (path.top() == w)

path.pop();

else

return;

id\[v = 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 <= N; i++)

if (pre\[i\] == -1)

scR(i);

void DFS(int w, int d)

int p = G\[w\].next;

d++;

pre\[w\] = 1;

if (d > cnt)

cnt = d;

while (p)

if (pre\[G\[p\].id\] != 1)

DFS(G\[p\].id, d);

p = G\[p\].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);

E\[i\].s = s;

E\[i\].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 = id\[E\[i\].s\];

e = id\[E\[i\].e\];

if (s != e)

in\[s\]++;

cnt = 0;

for (i = 0; i < scnt; i++)

if (in\[i\] == 0)

pos = i;

cnt++;

if (cnt != 1)

printf("0/n");

else

cnt = 0;

for (i = 1; i <= N; i++)

if (in\[id\[i\]\] == pos)

cnt++;

printf("%d/n", cnt);

int main()

while (scanf("%d %d", &N, &M) != EOF)

Solve();

return 0;

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

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 ACM模板——强连通分量

相关 tarjan对有向图的缩点(求强连通分量)

相关【算法与数据结构】——强连通分量

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

相关有向图的强连通分量之Tarjan算法

相关有向图(6)--计算强连通分量的Kosaraju算法

相关有向图强连通分量的Tarjan算法

相关图论：连通分量和强连通分量

相关温习Algs4 (四):有向图, 拓扑排序和强连通分量

相关图之强连通、强连通图、强连通分量 Tarjan算法