強連通分量

算法分類：

圖論

問題定義：

有向圖強連通分量：

在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通（strongly connected）。

如果有向圖G的每兩個頂點都強連通，則稱G是一個強連通圖。

非強連通圖有向圖的極大強連通子圖，成為強連通分量（strongly connected components）。

下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達，{5}，{6}也分别是兩個強連通分量。

直接根據定義，用雙向周遊取交際的方法求強連通分量，時間複雜度為O（N^2+M）。更好的方法是Kosaraju算法或者Tarjan算法。

兩者的時間複雜度都是O（N+M）。本文介紹的是Tarjan算法。

算法原理：（Tarjan）

Tarjan算法是基于對圖深度優先搜尋的算法，每個強連通分量為搜尋樹中的一顆子樹。

搜尋時，把目前搜尋樹中未處理的節點加入一個堆棧，回溯時可以盤對棧頂到棧中的節點是否為一個強連通分量。

定義DFN（u）為節點u搜尋的次序編号（時間戳）。Low（u）為u或者u的子樹能夠追溯到的最早的棧中的節點的次序号。

由定義可以得出：

Low（u）= Min { DFN（u）， Low（v）} （（u，v）為樹枝邊，u為v的父節點DFN（v），（u，v）為指向棧中節點的後向邊（非橫叉邊））

當DFN（u）=Low（u）時，以u為根的搜尋子樹上所有節點是一個強連通分量。

算法時空複雜度：

O（N+M）

代碼實作：（hdu1269）

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
using namespace
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 10005             // 題目中可能的最大點數
stack<int>sta;                // 存儲已周遊的結點
vector<int>gra[N];            // 鄰接表表示圖
int dfn[N];                 // 深度優先搜尋通路次序
int low[N];                 // 能追溯到的最早的次序
int InStack[N];             // 檢查是否在棧中(2為在棧中，1為已通路，且不在棧中，0為不在)
vector<int> Component[N];     // 獲得強連通分量結果
int InComponent[N];         // 記錄每個點在第幾号強連通分量裡
int index,ComponentNumber;  // 索引号，強連通分量個數
int n, m;                   // 點數，邊數

void init(void)
{
sizeof(dfn));
sizeof(low));
sizeof(InStack));
index = ComponentNumber = 0;
for (int
{
gra[i].clear();
Component[i].clear();
}

while(!sta.empty())
sta.pop();
}

void tarjan(int
{
Instack[u] = 2;
low[u] = dfn[u] = ++ index;
sta.push(u);

for (int
{
int
if
{
tarjan(t);
low[u] = MIN(low[u], low[t]);
}
else if
{
low[u] = MIN(low[u], dfn[t]);
}
}

if
{
++ ComponentNumber;
while
{
int
sta.pop();
InStack[j] = 1;
Component[ComponentNumber].push_back(j);
InComponent[j]=ComponentNumber;
if
binputak;
}
}
}

void input(void)
{
for(int
{
int
"%d%d",&a,&b);
gra[a].push_back(b);
}
}

void solve(void)
{
for(int
if(!dfn[i])
tarjan(i);
if(ComponentNumber>1)
"No");
else
"Yes");
}

int
{
while(scanf("%d%d",&n,&m),n+m)
{
init();
input();
solve();
}
}