圖的強連通分量
中優先佇列的用法
作者:dzf閱讀次數:87時間:2006-11-27 21:23:49演算法園地
這道題是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 algorithmby sempr ---- 2006.06.16*/
#include <>#include <>#define g_size 100000#define v_size 11000typedef struct graph graph;
typedef struct edge 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) //建立原圖和逆圖
void dfst(int x) //對逆圖進行搜尋
order[cnt++] = x;}
void dfsa(int x) //對原圖進行搜尋}
void solve() //主要過程
memset(vis, 0, sizeof(vis));cnt = 0;
for (i = 0; i < n; i++)}
memset(vis, 0, sizeof(vis));cnt = 0;
for (i = n - 1; i >= 0; i--)}
for (i = 0; i < m; i++)}
scnt = cnt;cnt = 0;
for (i = 0; i < scnt; i++)}
if (cnt != 1)else}
printf("%d\n", cnt);}}
int main()
gabow演算法/*
求有向圖的強連通分量的gabow『s algorithmby sempr ---- 2006.06.14*/
#include <>#include #include #define size 11000using namespace std;int n, m;
typedef struct node node;
typedef struct edgeedge;
edge e[size * 6];node g[size * 7];
int pre[size], id[size];typedef stack stack;stack s, path;int end;
int cnt, scnt;int vis[size];int in[size];
void insert(int s, int e)}
g[p].next = end;g[end].id = e;end++;}
void scr(int w)
void gabow()}}
void dfs(int w, int d)
while (p)
p = g[p].next;}}
void solve()
gabow();
memset(g, 0, sizeof(g));
memset(pre, 0, sizeof(pre));end = scnt + 10;
for (i = 0; i < m; i++)}
cnt = 0;
for (i = 0; i < scnt; i++)}
if (cnt != 1)else}
printf("%d\n", cnt);}}
int main()
return 0;}
《ACM程式設計與演算法》課程報告
2010 2011學年第2學期 acm程式設計與演算法 課程報告 班級 電氣0903 學號 20095690 姓名 劉星 格雷碼問題解題報告 一 研究報告 80分 1.題目描述 10分 在數字系統中只能識別0和1，各種資料要轉換為二進位制 才能進行處理，格雷碼是一種無權碼，採用絕對編碼方式，典型格雷...
演算法框圖 複數 推理與證明階段性測試題及解析
本試卷分第 卷 選擇題 和第 卷 非選擇題 兩部分 滿分150分 考試時間120分鐘 第 卷 選擇題共60分 一 選擇題 本大題共12個小題，每小題5分，共60分，在每小題給出的四個選項中，只有一項是符合題目要求的 1 2015 豫南九校聯考 複數的實部與虛部之和為 a 0 b 1 c 2 d 3 ...
甘肅省2023年公務員面試真題題目與解析
甘肅省2009年公務員面試真題題目與解析 名言人生哲理類 甘肅省2009面試公務員面試工作已經結束。甘肅省2009面試公務員面試真題主要集中在名言人生哲理 活動組織及疑難問題處理 對社會現象的看法與分析 個人情況與職務匹配四個方面。名言人生哲理類題目偏難，活動組織是常見題目比較簡單，疑難問題處理類難...