图论——强连通分量（Tarjan算法)

强连通分量

什么是强连通图？
如果一个有向图中，存在一条回路，所有的结点至少被经过一次，这样的图为强连通图。

什么是强连通分量？
在强连图图的基础上加入一些点和路径，使得当前的图不在强连通，称原来的强连通的部分为强连通分量。

求强连通分量有何作用？
在进行对其它图论问题的求解前，利用强连通分量的知识可以把图中强连通的点缩为一个点，减少接下来其它图论操作的计算。
在某些特定的环境下，求强连通分量变相地得出图中的环以及环的长度。

利用Tarjan算法求强连通分量

Tarjan算法的基本思路
首先考虑强连通分量的性质，即存在一条回路能从初始点又回到初始点。在这个查找的过程中，可以对经过的结点标记，当发现某一节点连向的点正好以及被标记过，则说明找到了一条回路，而这个回路上的所有点构成一个强连通分量。为了保存这个强连通分量，我们需要知道这条路上有哪些点，而此时，栈就是一种适合该算法的数据结构。对于每次搜索的点，我们都加入栈中，遇到回路时，在把栈中的元素逐个弹出，记录它们的起始结点，直到栈中弹出的元素正好是起始结点时，结束弹栈，继续搜索其它强连通分量。在这个过程中，所有的点和都有的边都被遍历了一次，所以最终的时间复杂度为$O(N+E)$

Tarjan算法的实现
为了实现这个过程，Tarjan算法需要装备如下几样东西：
记录搜索顺序的数组$dfn$；
记录所属强连通的数组$low$；
表示某结点是否在栈中的数组$instack$；
一个栈存储搜索路径；
从上面对Tarjan算法的描述中，很容易看出这个算法是基于深度优先搜索实现的。接下来，对Tarjan算法进行逐步推演。
（本人不喜欢使用网上用烂的素材，接下来包括以前的讲解图都是自己手画的，不喜勿喷）

tarjan(u) { 
    dfn[u]=low[u]=++Index stack.push(u) for each (u, v) in E if (v is not visted) tarjan(v) low[u] = min(low[u], low[v]) else if (v in S) low[u] = min(low[u], dfn[v]) if (dfn[u] == low[u]) repeat v = stack.pop print v until (u== v) } 

#include 
     #include 
     #include 
     using namespace std; int n,m,cnt,cntb; vector<int> edge[101]; vector<int> belong[101]; bool instack[101]; int dfn[101]; int low[101]; stack<int> s; void Tarjan(int u) { 
    ++cnt; dfn[u]=low[u]=cnt; s.push(u); instack[u]=true; for(int i=0;i<edge[u].size();++i) { 
    int v=edge[u][i]; if(!dfn[v]) { 
    Tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { 
    ++cntb; int node; do { 
    node=s.top(); s.pop(); instack[node]=false; belong[cntb].push_back(node); }while(node!=u); } } int main() { 
    cin>>n>>m; for(int i=1;i<=m;++i) { 
    int u,v; cin>>u>>v; edge[u].push_back(v); } Tarjan(1); cout<<"id :"; for(int i=1;i<=n;++i) cout<<i<<" "; cout<<endl; cout<<"dfn :"; for(int i=1;i<=n;++i) cout<<dfn[i]<<" "; cout<<endl; cout<<"low :"; for(int i=1;i<+n;++i) cout<<low[i]<<" "; cout<<endl; for(int i=1;i<=cntb;++i) { 
    cout<<"SCG "<<i<<" : "; for(int j=0;j<belong[i].size();++j) cout<<belong[i][j]<<" "; cout<<endl; } return 0; } 

按照先前的推演图，生成测试样例

来一道例题练手（USACO08DEC）

——题目描述——
每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

——输入格式——
第1行 整数n。

第2行到n+1行 每行包含一个整数 next_i 。

——输出格式——
n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。

——输入样例——
4
1
3
2
3

——输出样例——
1
2
2
3

——题解——
本题的数据量还是蛮大的，有$1e5$个结点，我们当然不可能对每一个结点进行深度优先搜索。幸运的是，每一个点都只有一条出边，也即意味着，本题中至少有一个环(包括自环)，而且，环上的点永远无法走出这个环，环上点的答案就是这个环的长度。而对于不在环上的点，用dfs直到找到一个环，其答案也即环的长度加上搜索到环的步数。环长度的计算，可以利用tarjan算法的思路，用dfn减去low。因地制宜，我写了一个简易版的tarjan.

——Code——

#include 
     #include 
     #include 
     using namespace std; int edge[]; int dfn[]; bool vis[]; int ans[]; stack<int> sta; int n; int cnt_dfn; void dfs(int u) { 
    ++cnt_dfn; dfn[u]=cnt_dfn; vis[u]=true; sta.push(u); if(vis[edge[u]]) { 
    if(!ans[edge[u]]) { 
    int val=dfn[u]-dfn[edge[u]]+1; int v; do { 
    v=sta.top(); ans[v]=val; sta.pop(); }while(v!=edge[u]); while(!sta.empty()) { 
    ++val; ans[sta.top()]=val; sta.pop(); } } else { 
    int val=ans[edge[u]]; while(!sta.empty()) { 
    ++val; ans[sta.top()]=val; sta.pop(); } } } else dfs(edge[u]); } int main() { 
    cin>>n; for(int i=1;i<=n;++i) { 
    cin>>edge[i]; if(edge[i]==i) { 
    ans[i]=1; vis[i]=true; } } for(int i=1;i<=n;++i) if(!vis[i]) { 
    cnt_dfn=0; dfs(i); } for(int i=1;i<=n;++i) cout<<ans[i]<<endl; return 0; } 

图论文章汇总