tarjan算法

  • 每次向下搜点,\(dfn[i]\)表示搜到第\(i\)点时的编号,\(low[i]\)表示第\(i\)个点能到达的最小的点的编号,我们在搜的时候可以把路径上的点存入到栈中,当\(dfn[i]=low[i]\)时,说明我们已经找完一个强连通子图了,此时就可以把栈中的元素出栈得到一个强连通子图.

  • 代码:

    #include <bits/stdc++.h>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    #define rep(a,b,c) for(int a=b;a<=c;++a)
    #define per(a,b,c) for(int a=b;a>=c;--a)
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
     
     int n,m;
     vector<int> edge[N];
     int dfn[N],low[N],timestamp;
     int stk[N],top;
     bool in_stk[N];
     int id[N],scc_cnt;
    
    void tarjan(int u){
        dfn[u]=low[u]=++timestamp;
        stk[++top]=u,in_stk[u]=true;
        for(auto w:edge[u]){
            if(!dfn[w]){
                tarjan(w);
                low[u]=min(low[u],low[w]);
            }
            else if(in_stk[w]) low[u]=min(low[u],dfn[w]);
        }
    
        if(dfn[u]==low[u]){
            ++scc_cnt;
            int y;
            do{
                y=stk[top--];
                in_stk[y]=false;
                id[y]=scc_cnt;
            }while(y!=u);
        }
    }
     
    int main(){
        ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        cin>>n>>m;
    
        rep(i,1,m){
            int u,v;
            cin>>u>>v;
            edge[u].pb(v);
        }
    
        rep(i,1,n){
            if(!dfn[i]) tarjan(i);
        }
     
        return 0;
    }
    
上一篇:STM32CubeMX HAL库+STM32F407+uCOS-III移植


下一篇:巨型星座try7_3(stk串口可见性报告)