强连通分量(一)——kosaraju

强连通分量主要有两种算法——kosaraju和tarjan。其中,两个算法的时间复杂度均为O(m+n),kosaraju算法更易于理解,而tarjan虽然概念更难,但是速度更快,更不容易爆栈超内存。本篇博客将介绍的是kosaraju算法。

一、相关概念

  1. 强连通:在有向图G中,如果两个顶点u,v间存在一条u到v的路径且也存在 一条v到u的路径,则称这两个顶点u,v是强连通的。
  2. 强连通图:如果有向图G的任意两个顶点都强连通,则称G是一个强连通图。
  3. 强连通分量:有向非强连通图的极大强连通子图,称为强连通分量。
  4. 极大强连通子图:若G是一个强连通子图且不是另一个强连通子图G’的真子集,则称G是一个极大强连通子图。

二、作用

强连通分量可以广泛运用在缩点的问题当中。缩点及在有些问题中,我们可以把几个可以互相到达的点视为一个点,大大减小问题的时间复杂度。eg:洛谷P2341

三、kosaraju算法

1.算法描述:

  • 基于两次DFS的有向图强联通子图算法。

2.算法原理:

首先对一个有向图G建立它的反向图G’(后面会讲到为什么),然后进行DFS,每次DFS将最后被访问完的节点放在dfn数组的最后面,因此将整个有向图G的所有节点进行遍历后,dfn数组的最后一个节点就是整个有向图G的其中一个子图最上方的节点。此时,选择具有最晚访问完的节点,对反向图G’进行DFS,删除能够遍历到的节点,这些顶点构成一个强联通分量。那么为什么这些定点构成了一个强连通分量呢?我们设当前dfn数组的最后一个节点为s。在第一次DFS中,我们已经保证了由s可以到达的所有点,所以这些顶点能不能构成强连通图取决于它们是否可以到达s。所以我们对反向图G’由s开始搜索,就可以找到能到达s的点。而最开始建立反向图G’的本质就是为了将判断一个节点是否可以到达s转换为了s是否能到达一个节点。最后,如果还有节点没有删除,那么就再找到dfn数组的最后一个节点重复以上步骤。由此,我们可以将kosaraju算法分解为以下步骤:

  1. 对原有向图G进行DFS,记录结点访问完的顺序dfn[i],dfn[i]表示第i个访问完的结点是dfn[i]。
  2. 选择具有最晚访问完的节点,对反向图G’进行DFS,删除能够遍历到的节点,这些顶点构成一个强联通分量
  3. 如果还有节点没有删除,继续第2步,否则算法结束。

3.代码实现

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int sum=0,ans=0;
int use[10005],dfn[10005];
int head[10005],top[10005];
struct node
{
    int u;
    int v;
    int next;
}w[100005],ww[100005];
void ins1(int u,int v,int score)//邻接表不解释
{
    w[score].u=u;
    w[score].v=v;
    w[score].next=head[u];
    head[u]=score;
    return;
}
void ins2(int u,int v,int score)//邻接表不解释
{
    ww[score].u=u;
    ww[score].v=v;
    ww[score].next=top[u];
    top[u]=score;
    return;
}
void dfs1(int k)
{
    use[k]=1;
    int d=head[k];
    while(d!=0)
    {
        if(!use[w[d].v])
            dfs1(w[d].v);
        d=w[d].next;
    }
    dfn[++sum]=k;//当当前节点被访问完后加入dfn中
    return;
}
void dfs2(int k)
{
    use[k]=1;
    int d=top[k];
    while(d!=0)
    {
        if(!use[ww[d].v])
            dfs2(ww[d].v);
        d=ww[d].next;
    }
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        cin>>a>>b;
        ins1(a,b,i);//邻接表建立正向图G
        ins2(b,a,i);//邻接表建立反向图G'
    }
    for(int i=1;i<=n;++i)
        if(!use[i])//若当前节点没有被访问到
            dfs1(i);//第一次dfs
    memset(use,0,sizeof(use));//清空数组重复利用节省空间,接下来用use记录是否被删除
    for(int i=n;i>=1;--i)
        if(!use[dfn[i]])//按照dfn的顺序进行访问
        {
            ans++;//若一个节点还没有被删除,说明其所在的强连通分量还没有被找到
            dfs2(vis[i]);//第二次dfs
        }
    cout<<ans;//输出当前图中强连通分量的个数
    return 0;
}

讲到这里,kosaraju算法就结束了。建议做的题有:HDU1269

发表评论

电子邮件地址不会被公开。 必填项已用*标注