每次向下搜点,\(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;
}