tarjan算法有向图求强连通分量模板

佚名 4年前 (2020-06-02) 算法 570人围观抢沙发百度已收录

强连通：在有向图中，如果Vx能到达Vy，且Vy也能到达Vx，说明它们两个点强连通。

强连通分量：在有向图中，存在一个极大子图，该子图中任意两点都是强连通。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>

using namespace std;

#define ll long long
#define pb push_back
#define fi first
#define se second

const int N = 1e4 + 10;
int dfn[N]; //时间戳
int low[N]; //能到达最早点
int s[N]; //栈
int ins[N]; //是否在栈内
int scc_no[N];//属于哪个scc
int scc_cnt[N]; //该scc有几个点
vector<int > scc[N];//缩点
vector<int > E[N]; //边
vector<int > new_E[N];//缩点后的图
int SCC; //第几个scc
int tim;//dfs序号
int top;//栈顶
int n, m; //点数  边数


//时间复杂度  O(m)

void init(int n){
    for(int i = 1; i <= n; ++i){
        dfn[i] = low[i] = ins[i] = 0;
        scc_cnt[i] = 0;
        scc_no[i] = 0;
        scc[i].clear();
        E[i].clear();
        new_E[i].clear();
    }
    SCC = tim = top = 0;
}

void tarjan(int now){
    dfn[now] = low[now] = ++tim;
    ins[now] = 1; s[top++] = now;

    for(auto to : E[now]){
        if(!dfn[to]){
            tarjan(to);
            low[now] = min(low[now], low[to]);
        }else if(ins[to]){
            //侧边，形成环
            low[now] = min(low[now], dfn[to]);
        }
    }

    if(dfn[now] == low[now]){
        int sum = 0; //该scc的点数
        ++SCC;//第几个scc
        int tmp;//暂存点

        do{
            tmp = s[--top];//取点
            ins[tmp] = 0;//出栈
            ++sum;//点数++
            scc_no[tmp] = SCC;//属于哪个scc
            scc[SCC].pb(tmp);//放入这个连通图，缩点
        }while(tmp != now);
        scc_cnt[SCC] = sum;//该scc的点数
    }
}


void show_info(){
    //每个点属于哪个scc
    cout << endl << "-------------------" << endl;
    for(int i = 1; i <= n; ++i){
        printf("id = %d  scc_no = %d\n", i, scc_no[i]);
    }
    //每个scc包含几个点
    cout << endl << "-------------------" << endl;
    for(int i = 1; i <= SCC; ++i){
        printf("SCC = %d   cnt = %d\n", i, scc_cnt[i]);
        
        //这个scc中点的信息
        printf("have point : ");
        for(auto poi : scc[i]){
            printf("(%d) ", poi);
        }
        cout << endl << endl;
    }
    cout << endl << "-------------------" << endl;
    //新图的边
    for(int i = 1; i <= SCC; ++i){
        printf("id = %d: to : ", i);
        for(auto v : new_E[i]){
            printf("(%d) ", v);
        }printf("\n");
    }   
    cout << endl << "-------------------" << endl;
}

void solve(){

    while(~scanf("%d%d", &n, &m)){
        //scanf("%d%d", &n, &m);
        //初始化每组数据
        init(n);
        
        //读边
        for(int i = 1; i <= m; ++i){
            int u, v;
            scanf("%d%d", &u, &v);
            E[u].pb(v);
        }

        //可能不是一个连通图
        for(int now = 1; now <= n; ++now){
            if(!dfn[now]){
                tarjan(now);
            }
        }

        //新图建边
        for(int now = 1; now <= n; ++now){
            for(auto to : E[now]){
                if(scc_no[now] != scc_no[to]){
                    new_E[scc_no[now]].pb(scc_no[to]);
                }
            }
        }

        //tarjan（）过后的信息展示
        show_info();

    }
}

int main(){
    
    solve();    
    //cout << "not error" << endl;
    return 0;
}