强连通分量算法之——Tarjan
还是POJ_2762,前段时间用Kosaraju算法解决掉了，不过解决强连通分量的线性时间复杂度的算法还有两个，Tarjan，Gabow，今天把Tarjan看了下，感觉基本思想还是不难的，实现起来也算容易，不过我还不能证明其正确性。
Tarjan算法的基本思路就是，利用DFS去求强连通分量，具体步骤如下：
1.任意选取一个顶点做为DFS的起始位置，进行DFS。
2.在每次DFS中，先把discoverTime[now_node]，和lowlink[now_node]赋值为当前搜索时间，并把当前结点压入栈内，然后查看当前结点的所有后继结点，如果其后继结点尚未访问，则继续DFS下去，并且lowlink[now_node] = min(lowlink[now_node]，lowlink[当前结点的后继]).否则就检查该后继结点是否还在栈中,如果是的话则有 lowlink[now_node] = min(lowlink[now_node],discoverTime[该后继结点]);
说明:lowlink[u]表示包括u结点及其所有后继结点中最早被发现的时间，discoverTime[u]表示u结点的被发现时间.
3.查看lowlink[now_node]是否等于discoverTime[now_node]，如果是，则说明该结点是一个强连通分量的根，则把栈中的元素弹出，直到弹出的元素是now_node为止。至此就求出了一个SCC。
4.如果图中尚有未被访问的结点，那么就以这些结点中的任意一个作为起始位置，再次进行DFS，回到步骤二，直到所有结点都被访问过。至此，图的所有SCC都被求出.
伪代码如下：
algorithm tarjan is input: graph G = (V, E) output: set of strongly connected components (sets of vertices) index := 0 S := empty for each v in V do if (v.index is undefined) then strongconnect(v) end if repeat function strongconnect(v) // Set the depth index for v to the smallest unused index v.index := index v.lowlink := index index := index + 1 S.push(v) // Consider successors of v for each (v, w) in E do if (w.index is undefined) then // Successor w has not yet been visited; recurse on it strongconnect(w) v.lowlink := min(v.lowlink, w.lowlink) else if (w is in S) then // Successor w is in stack S and hence in the current SCC v.lowlink := min(v.lowlink, w.index) end if repeat // If v is a root node, pop the stack and generate an SCC if (v.lowlink = v.index) then start a new strongly connected component repeat w := S.pop() add w to current strongly connected component until (w = v) output the current strongly connected component end if end function
POJ_2762_Tarjan实现代码如下:
#include<iostream>#include<vector>#include<stack>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 1001;vector<int> g[MAXN];//adjliststack<int> S;int vis[MAXN],store[MAXN],scc[MAXN][MAXN],scccnt,DFN[MAXN],LOW[MAXN],belong[MAXN],deg[MAXN];#define MIN(a,b) a>b?b:avoid addEdge(int u,int v){ g[u].push_back(v);}void init(){ for(int i=0;i<MAXN;i++)g[i].clear(); while(!S.empty())S.pop(); memset(vis,0,sizeof(vis)); memset(store,0,sizeof(store)); memset(scc,0,sizeof(scc)); scccnt = 0;}void tarjan(int u,int n,int &time){ DFN[u] = LOW[u] = time++; S.push(u); vis[u] = 1;store[u] = 1; for(int i=0;i<g[u].size();i++) { if(!vis[g[u][i]])//not visited { tarjan(g[u][i],n,time); LOW[u] = MIN(LOW[u],LOW[g[u][i]]); } else if(store[g[u][i]])//in the stack { LOW[u] = MIN(LOW[u],DFN[g[u][i]]); } } if(LOW[u]==DFN[u]) { int v; do { v = S.top(); S.pop(); store[v] = 0;//out from the stack belong[v] = scccnt; }while(v!=u); scccnt++; }}void make_SCCG(int n){ for(int i=1;i<=n;i++) { for(int j=0;j<g[i].size();j++) { if(belong[i]!=belong[g[i][j]]) { scc[belong[i]][belong[g[i][j]]]=1; } } }}bool calldfs2(int n){ memset(vis,0,sizeof(vis)); make_SCCG(n); memset(vis,0,sizeof(vis)); memset(deg,0,sizeof(deg)); for(int i=0;i<scccnt;i++) { for(int j=0;j<scccnt;j++) { if(scc[j][i])deg[i]++; } } int u,cnt; for(int i=0;i<scccnt;i++) { cnt = 0; for(int j=0;j<scccnt;j++) { if(deg[j]==0&&!vis[j]) { u = j; cnt++; } } if(cnt!=1)return false; vis[u] = 1; for(int j=0;j<scccnt;j++) { if(scc[u][j])deg[j]--; } } return true;}int main(){ int n,m,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); addEdge(a,b); } int time = 1; for(int i=1;i<=n;i++) { if(!vis[i])tarjan(i,n,time); } bool ok = calldfs2(n); if(ok) printf("Yes\n"); else printf("No\n"); } return 0;}
参考资料:
[url]http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#Overview [/url]