图的连通性:有向图强连通分量-Tarjan算法

参考资料:http://blog.csdn.net/lezg_bkbj/article/details/11538359

上面的资料,把强连通讲的很好很清楚,值得学习。

在一个有向图G中,若两顶点间至少存在一条路径(即a能到b,b也能到a),则称两个顶点强连通;如果该有向图G中任意两顶点都强连通,则称G为强连通图;在一个非强连通图中,若有子图是强连通图,则称该子图为强连通分量


有向图强连通分量+链式前向星 模板如下:

const int MAXN=110;
const int MAXM=10010; struct edge
{
int next,to;
}E[MAXN]; int head[MAXN],Ecou; //Ecou:边下标
int Stack[MAXN],top; //top:栈顶
int Belong[MAXN],Bcnt; //Bcnt:强连通分量个数
int Index; //Index:时间戳
int DFN[MAXN],LOW[MAXN];
bool inStack[MAXN]; void add_edge(int u,int v)
{
E[Ecou].to=v;
E[Ecou].next=head[u];
head[u]=Ecou++;
} void Tarjan(int u)
{
int v; LOW[u]=DFN[u]=++Index;
Stack[top++]=u;
inStack[u]=true;
for(int i=head[u];i!=-1;i=E[i].next)
{
v=E[i].to;
if(!DFN[v])
{
Tarjan(v);
if(LOW[u]>LOW[v])
LOW[u]=LOW[v];
}
else if(inStack[v]&&LOW[u]>DFN[v])
LOW[u]=DFN[v];
}
if(LOW[u]==DFN[u])
{
++Bcnt;
do
{
v=Stack[--top];
inStack[v]=false;
Belong[v]=Bcnt;
}while(v!=u);
}
} void getSCC(int n)
{
for(int i=1;i<=n;i++)
if(!DFN[i])
Tarjan(i);
} void init(int n)
{
Ecou=Index=Bcnt=top=0;
for(int i=1;i<=n;i++)
{
head[i]=-1;
DFN[i]=LOW[i]=Belong[i]=0;
inStack[i]=0;
}
}

模板题:HDU 1269 迷宫城堡

上一篇:setObject与setValue的区别


下一篇:extJS4.2.0 tabPanel学习(三)