强连通分量
概念
1.连通：在有向图中，若存在点a到达点b的有向路径并且存在点b到达点a的有向路径，则点a和点b是（强）连通的。
2.强连通图：如果有向图G中的任意两点都是强连通的，则图G为强连通图，如图2。
3.强连通分量：有向图G中最大的强连通子图为其强连通分量。例如，图一中，{A,B,C}和{D}就是图一的两个强连通分量。
强连通分量
Tarjan算法
Tarjan算法是基于DFS搜索的是时间复杂度为O（n）的计算强连通分量的算法。
-
原理
在图G中若点A，B是强连通的则以AB之间的有向路径构成一个环路，以其上任一点为C起点进行DFS搜索必定会找到起点C。Tarjan算法就是通过一个数组LOW来记录环路的起点，在环路中的每个顶点都是该强连通分量的一部分。
-
具体步骤
首先需要定义两个全局数组LOW和DFN，其中DFN记录当前节点DFS的标号，LOW记录当前节点DFS所能到达的最小的的节点标号。还要定义一个全局栈STACK用来保存正在处理的节点。
选定一个初始节点s，利用Tarjan求强连通分量。将该点的编号设为1,此时LOW[s]=DFN[s]=1，并将该点压栈;然后，遍历其相临节点，递归调用Tarjan算法。比较每次调用Tarjan算法DFN[i]的值比DFN[i-1]的值大一。遍历完子节点后LOW值更新为子节点中LOW最小的节点的LOW值。
然后弹栈直到LOW等于DFN，弹出的元素处于同一连通分量中。
-
代码
//hdu-1269 迷宫城堡
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;
const int MAX_N=10100;
vector<int> G[MAX_N];
int isStack[MAX_N];
int dfn[MAX_N],low[MAX_N],vis[MAX_N],color[MAX_N];
int d_num=0;
int now=1;
int ans=0;
int n,m;
stack <int> stk;
void tarjan(int s){
dfn[s]=low[s]=++d_num;
vis[s]=1;
stk.push(s);
isStack[s]=1;
for(int i=0;i<G[s].size();i++){
if(!vis[G[s][i]]){
tarjan(G[s][i]);
low[s]=min(low[s],low[G[s][i]]);
}
else{
if(isStack[G[s][i]])
low[s]=min(low[s],low[G[s][i]]);
}
}
if(low[s]!=dfn[s])
return;
int tmp=stk.top();
stk.pop();
while(low[tmp]!=dfn[tmp]){
isStack[tmp]=0;
color[tmp]=now;
tmp=stk.top();
stk.pop();
}
color[tmp]=now;
now++;
return;
}
int main(){
while(scanf("%d%d",&n,&m)){
if(n==0)
break;
ans=0;
d_num=0;
now=1;
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(color,0,sizeof(color));
memset(low,0,sizeof(low));
memset(isStack,0,sizeof(isStack);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
}
tarjan(1);
for(int i=1;i<=n;i++){
if(color[i]==1)
ans++;
}
if(n==ans)
printf("Yes\n");
else
printf("No\n");
for(int i=0;i<=n;i++){
G[i].clear();
}
}
return 0;
}
