您的位置: 首页  >  文章  >  强连通分量&&缩点算法

强连通分量&&缩点算法

分类: 文章 • 2024-04-19 21:38:46

参考博客：强连通图的算法

模板题：刻录光盘、间谍网络

定义

  1. 强联通图：　　在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。
  2. 强连通分量：　　非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

示意图

强连通分量&&缩点算法

Tarjan算法

  1. 时间复杂度：O(N+M)
  2. 原理：Tarjan算法是基于对图深度优先搜索的算法，
  3. 每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索被搜索到时的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。
  4. 算法演示
    1. 从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。强连通分量&&缩点算法

    2. 返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。强连通分量&&缩点算法

    3. 返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。强连通分量&&缩点算法

    4. 继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。强连通分量&&缩点算法

    5. 至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

      可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。

  5. 代码 
    #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct Edge
{
    int to,next;
} E[8010];
int T[3010];
int Head[3010],idx[3010],num,num_Edge,depth;
int N,M,P,Ans=0;
int in[3010],V[3010];
//vector<int>Path,Root;
vector<int>S;
void Add_Edge(int from,int to)
{
    ++num_Edge;
    E[num_Edge].next=Head[from];
    E[num_Edge].to=to;
    Head[from]=num_Edge;
}
int DFN[3010],LOW[3010];
bool vis[3010];
void Tarjan(int x)
{
    DFN[x]=LOW[x]=(++num);
    S.push_back(x);
    vis[x]=1;//表示x在栈中
    for(int i=Head[x]; i; i=E[i].next)
    {
        if(DFN[E[i].to]==-1)
        {
            Tarjan(E[i].to);
            LOW[x]=min(LOW[E[i].to],LOW[x]);
        }
        else if(vis[E[i].to]) LOW[x]=min(DFN[E[i].to],LOW[x]);
    }
    if(LOW[x]==DFN[x])
    {
        ++depth;
        //printf("\n");
        while(S.back()!=x)
        {
            //    printf("%d ",S.back());
            idx[S.back() ]=depth;
            vis[S.back()]=0;
            V[depth]=min(V[depth],T[S.back() ]);
            S.pop_back();
        }
        //printf("%d\n",S.back());
        idx[S.back() ]=depth;
        vis[S.back()]=0;
        V[depth]=min(V[depth],T[S.back() ]);
        S.pop_back();

    }
}
/*void Gabow(int x)
{
    Order[x]=(++num);
    Path.push_back(x);
    Root.push_back(x);
    for(int i=Head[x]; i; i=E[i].next)
    {
        if(Order[E[i].to]==-1)     Gabow(E[i].to );
        else if(idx[E[i].to]==-1&&Order[E[i].to]!=-1) while(Order[Root.back()]>Order[E[i].to]) Root.pop_back();
    }
    if(Root.back()==x)
    {
        Root.pop_back();
        ++depth;
        int Top;
        do
        {
            Top=Path.back();
            idx[Top]=depth;
            V[depth]=min(V[depth],T[Top]);

            Path.pop_back();
        }
        while(Top!=x);
    }
}*/
int main(void)
{
    memset(idx,-1,sizeof(idx));
    memset(DFN,-1,sizeof(DFN));
    scanf("%d",&N);
    scanf("%d",&P);
    for(int i=1; i<=N; ++i) V[i]=1e9+7,T[i]=1e9+7;
    for(int i=1; i<=P; ++i)
    {
        int t;
        scanf("%d",&t );
        scanf("%d",&T[t]);
    }
    scanf("%d",&M);
    for(int i=1; i<=M; ++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        Add_Edge(u,v);
    }
    for(int i=1; i<=N; ++i)
        if( DFN[i]==-1&&T[i]!=1e9+7) Tarjan(i);//Gabow(i);
    for(int i=1; i<=N; ++i)
    {
        if(DFN[i]==-1)
        {
            printf("NO\n%d",i);
            return 0;
        }
    }
    for(int i=1; i<=depth; ++i) in[i]=true;
    for(int i=1; i<=N; ++i)
        for(int j=Head[i]; j; j=E[j].next)
            if(idx[i]!=idx[E[j].to]) in[idx[E[j].to]]=false;
    for(int i=1; i<=depth; ++i)
        if(in[i]&&V[i]!=1e9+7) Ans+=V[i];
    printf("YES\n%d",Ans);
    return 0;
}

     

Gabow算法

  1. 原理：Gabow算法是Tarjan算法的提升版本，该算法类似于Tarjan算法。算法维护了一个顶点栈，但是还是用了第二个栈来确定何时从第一个栈中弹出各个强分支中的顶点，它的功能类似于Tarjan算法中的数组low。从起始顶点w处开始进行DFS过程中，当一条回路显示这组顶点都属于同一个强连通分支时，就会弹出栈二中顶点，只留下回边的目的顶点，也即搜索的起点w。当回溯到递归起始顶点w时，如果此时该顶点在栈二顶部，则说明该顶点是一个强联通分量的起始顶点，那么在该顶点之后搜索的顶点都属于同一个强连通分支。于是，从第一个栈中弹出这些点，形成一个强连通分支。
  2. 代码 
    #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
struct Edge
{
    int to,next;
} E[21000];
vector<int>Path,Root;
int DFN[210],num=0,Head[210],num_Edge,idx[210],depth;
bool vis[210],in[210];
void Add_Edge(int from,int to)
{
    ++num_Edge;
    E[num_Edge].to=to;
    E[num_Edge].next=Head[from];
    Head[from]=num_Edge;
}
void Gabow(int x)
{
    DFN[x]=(++num);//记录访问顺序
    Path.push_back(x),Root.push_back(x)  ;//压入栈中
    for(int i=Head[x]; i; i=E[i].next)
    {
        if(DFN[E[i].to]==-1) Gabow(E[i].to);//若下一个顶点未被访问，
        else if(idx[E[i].to]==-1&&DFN[E[i].to]!=-1)//若下一顶点已被访问，且未被划分强联通分量
            while(DFN[Root.back()]>DFN[E[i].to]) Root.pop_back();//弹出到E[i].to之前的点
    }
    if(Root.back()==x)   //若Root栈顶元素等于x
    {
        Root.pop_back();
        ++depth;
        int Top;
        do
        {
            Top=Path.back();
            idx[Top]=depth;
            Path.pop_back();
        }
        while(Top!=x);
    }
}
int main()
{
    memset(idx,-1,sizeof(idx));
    memset(DFN,-1,sizeof(DFN));
    int N,u,Ans=0;
    scanf("%d",&N);
    for(int i=1; i<=N; ++i) while(scanf("%d",&u)&&u) Add_Edge(i,u);//输入
    for(int i=1; i<=N; ++i)//开始Gabow
        if(DFN[i]==-1) Gabow(i);
    for(int i=1; i<=depth; ++i) in[i]=true;//割点
    for(int i=1; i<=N; ++i)
        for(int j=Head[i]; j; j=E[j].next)
            if(idx[i]!=idx[E[j].to]) in[idx[E[j].to]]=false;
    for(int i=1; i<=depth; ++i) if(in[i]) ++Ans;
    printf("%d",Ans);
    return 0;
}

     

相关推荐