有向图的强连通分量

说明

学习资料:

概念:

有向图强连通分量在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

使用方法

  • work()函数

Tips

  • 自行挑需要的东西写,如果附加的信息太多可能会MLE
  • 一般都要缩点成为DAG,然后再做一些操作
  • 对于scc_cnt == 1的情况偶尔需要特判

模版

const int maxn=5000+10;
int dfs_clock;//时钟
int scc_cnt;//强连通分量总数
vector<int> G[maxn];//G[i]表示i节点指向的所有点
vector<int> belong[maxn];//belong[i]表示第i个强联通分量包含的所有元素 下标1~scc_cnt
int pre[maxn]; //时间戳
int low[maxn]; //u以及u的子孙能到达的祖先pre值
int sccno[maxn];//sccno[i]==j表示i节点属于j连通分量 sccno[i]的区间为1~scc_cnt
int cnt[maxn];
stack<int> S;
void dfs(int u){
    pre[u]=low[u]=++dfs_clock;
    S.push(u);
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u]=min(low[u],pre[v]);
        }
    }
    if(low[u] == pre[u]){//u为当前强连通分量的入口
        scc_cnt++;
        belong[scc_cnt].clear();
        while(true){
            int x=S.top(); S.pop();
            sccno[x]=scc_cnt;
            cnt[scc_cnt]++;
            belong[scc_cnt].push_back(x);
            if(x==u) break;
        }
    }
}
//求出有向图所有连通分量
void find_scc(int n){
    scc_cnt=dfs_clock=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++)
        if(!pre[i]) dfs(i);
}
void work(int n,int m){
    for(int i=1;i<=n;i++) G[i].clear();
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);//index range: 1~n
        G[u].push_back(v);
    }
    find_scc(n);
    for(int i=1;i<=n;i++)
        printf("%d号点属于%d分量\n",i,sccno[i]);
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        work(n,m);
    }
}

results matching ""

    No results matching ""