【算法与数据结构】——强连通分量

阳光穿透心脏的1/2处 2022-10-14 08:41 157阅读 0赞

## 强连通分量 ##

在一个有向图中，选取一个点集S，如果对于S中的任意两点u,v都满足u可到达v，则称S是强连通的。

如果一个强连通点集S中，不能在加入更多的点使得它仍然强连通，则称S是强连通分量。

## 例题 ##

给定一个有向图，统计有多少点对u,v(u<v)满足：u可以到达v，且v可以到达u。

## Tarjan算法 ##

## Kosaraju算法求强连通分量 ##

**无向图：** 在无向图中，求解连通分量只需要按照1到n的顺序依次考虑每个点。  
考虑到i点时，如果i点未被访问过，就说明找到了一个新的连通分量，从i点开始DFS即可找到i所在的连通分量。  
**有向图：**  
在有向图中，使用上述方法就是不正确的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]  
Kosaraju算法思想：

1.  把图中所有边反向，再按照1到n的顺序去DFS（后序遍历），得到每个点的出栈序列q。
2.  按照q\[n\]…q\[1\]的顺序去DFS原图就是一个合法的顺序。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 1]

因为把边方向已否不改变强连通分量，所以得到一个简化的Kosaraju算法：

1.  按照1到n的顺序去DFS后续遍历原图，得到每个点的出栈序列q。
2.  按照q\[n\]…q\[1\]的顺序去DFS反图，依次得到每个强连通分量。

源码：

void dfs1(int x){
    vis[x] = 1;
    for(int i = G[0][x];i;i=NXT[0][i])
    if(!vis[V[0][i]])
    dfs1(V[0][i]);
    q[++t] = x;
    }
    void dfs2(int x,int y)
    {
    vis[x]=0;
    f[x]=y;
    for(itn i = G[1][x];i;i=NXT[1][i])
    if(vis[V[1][i]])dfs2(V[1][i],y);
    }
    int main()
    {
    for(t=0,i=1;i<=n;i++)
    if(vis[V[1][i]])
    dfs2(V[1][i],y);
    }
    int main(){
    for(t=0,i=1;i<=n;i++）
    if(!vis[i])dfs1(i);
    for(i = n;i;i--)
    if(vis[q[i]])
    dfs2(q[i],q[i]);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]: /images/20221014/840be4b88fdf477d853cb84f20845be6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 1]: /images/20221014/95844909f7c641198776e4e361331ba7.png