复习心得 - 强连通分量

· · 算法·理论

强连通分量 \tt SCC

图变为无向图可以互相到达的点集是弱连通分量。

任意两点可以互相可达的一个点集是强联通分量。

Tarjan 算法

边 dfs 边能形成 \tt SCC 就切分。

具体的：

  1. 要是没有访问过，dfn_v=0，我们继续搜下去，我们要更新一个追溯值 low_v\to low_p，最早可以追溯到哪里。
  2. 否则要是这个点放入了当前的 \tt SCC，那么 dfn_v\to low_p，找到当前 \tt SCC 的最早追溯值。

然后我们发现可能这个点终结了这个 \tt SCC，即 dfn_p=low_p。

那么，我们从当前栈中找点，一直找到当前点 p，我们就取出了一个 \tt SCC。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,dfn[N],did,top,st[N],low[N],in[N],scid;
vector<int>e[N];
vector<vector<int>>scc;
void dfs(int p){
    st[++top]=p;
    ++did;
    low[p]=did;
    dfn[p]=did;
    in[p]=1;
    for(auto v:e[p]){
        if(!dfn[v]){
            dfs(v);
            low[p]=min(low[p],low[v]);
        }else if(in[v])
            low[p]=min(low[p],dfn[v]);
    }
    if(low[p]==dfn[p]){
        int now;
        vector<int>ns;
        do{
            now=st[top];
            in[now]=0;
            ns.push_back(now);
            --top;
        }while(now!=p);
        sort(ns.begin(),ns.end());
        scc.push_back(ns);
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])
        dfs(i); 
    sort(scc.begin(),scc.end());
    for(auto sc:scc){
        for(auto v:sc)cout<<v<<" ";
        cout<<"\n";
    }
    return 0;
}

Kosaraju 算法

这个不太多人知道的算法是这样的：

  1. 首先正着 dfs 一次，搞出出栈序列。
  2. 然后按照出栈序列从后往前搜，每一次要是没被搜过说明是汇点，从这个点开始搜，最后求出强联通分量。

为什么是汇点呢？我们发现最后出栈那么说明所属强连通分量已经出栈了，肯定可以作为汇点去搜出原来的强连通分量。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,vis[N],st[N],top;
vector<int>e[N],g[N],c;
vector<vector<int>>scc;
void dfs(int p){
    vis[p]=1;
    for(auto v:e[p])if(!vis[v])
        dfs(v);
    st[++top]=p;
}
void dfs2(int p){
    vis[p]=1;
    for(auto v:g[p])if(!vis[v])
        dfs2(v);
    c.push_back(p);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)if(!vis[i])
        dfs(i); 
    for(int i=1;i<=n;i++)
        vis[i]=0;
    for(int i=n;i>=1;i--)if(!vis[st[i]]){
        c.clear();
        dfs2(st[i]);
        sort(c.begin(),c.end());
        scc.push_back(c);
    }
    sort(scc.begin(),scc.end());
    for(auto sc:scc){
        for(auto v:sc)cout<<v<<" ";
        cout<<"\n";
    }
    return 0;
}