【模板】Tarjan

Andy1101 · 2025-10-25 18:56:34 · 个人记录

强连通分量

int dfn[N] , low[N];
int id[N];
int idx;
int clk;
bool vis[N];
vector<int> adj[N];
stack<int> stk;
void dfs(int u)
{
    stk.push(u);
    dfn[u]=low[u]=++clk;
    for(auto v:adj[u])
    {
        if(!dfn[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!id[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        idx++;
        int x;
        do{
            x=stk.top();
            stk.pop();
            id[x]=idx;
            ans[idx].push_back(x);
        }while(x!=u);
    }
}
若id[i]=id[j]，那么i和j属于同一个强连通分量

缩点

int dfn[N] , low[N];
int id[N];
int idx;
int cnt;
bool vis[N];
vector<int> adj[N] , ans[N];
stack<int> stk;
void dfs(int u)
{
    stk.push(u);
    dfn[u]=low[u]=++cnt;
    for(auto v:adj[u])
    {
        if(!dfn[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!id[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        idx++;
        int x;
        do{
            x=stk.top();
            stk.pop();
            id[x]=idx;
            ans[idx].push_back(x);
        }while(x!=u);
    }
}
int main()
{
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) dfs(i);
    }
    for(int u=1;u<=n;u++)
    {
        for(auto v:adj[u])
        {
            if(id[u]!=id[v])
            {
                E[id[u]].push_back(id[v]); 
            }
        }
    }
    return 0;
}
此时E就是缩点之后的点

割点

vector<int> adj[N];
int dfn[N],low[N];
int clk;
int ans;
int a[N];
void dfs(int u,int p)
{
    dfn[u]=low[u]=++clk;
    int cnt=0;
    bool iscut=false;
    for(auto v:adj[u])
    {
        if(dfn[v])
        {
            low[u]=min(low[u],dfn[v]);
            continue;
        }
        cnt++;
        dfs(v,u);
        low[u]=min(low[u],low[v]);
        if(p!=-1 && low[v]>=dfn[u]) iscut=true; 
    }
    iscut=iscut || (p==-1 && cnt>1);
    if(iscut) a[++ans]=u;
}
此时a数组中就是所有的割点

割边

vector<int> adj[N];
int dfn[N] , low[N];
int clk;
vector<pair<int,int>> ans;
void dfs(int u,int p)
{
    dfn[u]=low[u]=++clk;
    for(auto v:adj[u])
    {
        if(v==p) continue;
        if(dfn[v])
        {
            low[u]=min(low[u],dfn[v]);
            continue;
        }
        dfs(v,u);
        if(low[v]>dfn[u]) ans.push_back({u,v});
        low[u]=min(low[u],low[v]);
    }
}
此时ans中就是所有的割边

点双连通分量

vector<node> adj[N];
int dfn[N],low[N];
bool vis[N];
int id[N];
stack<int> stk;
int idx;
int clk;
void dfs(int u,int p)
{
    stk.push(u);
    dfn[u]=low[u]=++clk;
    for(auto x:adj[u])
    {
        if(vis[x.id]) continue;
        int v=x.v;
        if(dfn[v])
        {
            low[u]=min(low[u],dfn[v]);
            continue; 
        }
        vis[x.id]=true;
        dfs(v,u);
        if(low[v]>dfn[u])
        {
            idx++;
            while(1)
            {
                int x;
                x=stk.top();
                stk.pop();
                id[x]=idx;
                if(x==v) break;
            }
        }
        low[u]=min(low[u],low[v]);
    }
    if(p==-1)
    {
        idx++;
        while(!stk.empty())
        {
            int x=stk.top();
            stk.pop();
            id[x]=idx;
        }
    }
}