Tarjan算法

Tarjan算法中几个关键点:

  • dfn数组：dfn[u]表示结点u的深度优先次序

  • low数组：low[u]表示以u为根节点的最近的子节点的次序

  • stack数组：模拟栈

  • instack数组：对属于同一个强连通分量的点进行染色

当dfn[u]和low[u]相等时说明，找到一个强连通分量，这时需要进行弹栈操作，并将同一个连通分量中的所有点都缩成一个点，也就是常说的缩点操作

代码模板:

下面这个是将缩好的点看成一个新的图，然后判断如何连通

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e7+5;
int dfn[maxn],low[maxn],head[maxn],sstack[maxn],t[maxn],in[maxn];
int cnt,num,n,tot,tt,m;
bool instack[maxn];

struct edge{
    int to,next;
}e[maxn];

void add_edge(int u,int v){
    e[cnt].next = head[u];
    e[cnt].to = v; 
    head[u] = cnt++;
}

void tar(int u){
    dfn[u] = low[u] = ++tot;
    instack[u] = true;
    sstack[++num] = u;
    for(int i = head[u] ; i != -1 ; i = e[i].next){
        int v = e[i].to;
        if(!dfn[v]){
            tar(v);
            low[u] = min(low[u],low[v]);
        }
        else if(instack[v]) low[u] = min(dfn[v],low[u]);
    }
    if(dfn[u] == low[u]){
        while(u != sstack[num]){
            instack[sstack[num]] = false;
            t[sstack[num]] = tt;
            num--;
        }
        instack[u] = false;
        t[u] = tt;
        tt++;
        num--;
    }
}

int main(){
    cin >> n >> m;
    memset(head,-1,sizeof(head));
    memset(instack,false,sizeof(instack));
    for(int i = 0 ; i < m ; i++){
        int u,v;
        cin >> u >> v;
        if(u != v)
            add_edge(u,v);
    }
    for(int i = 1 ; i <= n ; i++){
        if(!dfn[i]) tar(i);
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i++){
        for(int j = head[i] ; j != -1 ; j = e[j].next){
            int v = e[j].to;
            if(t[i] != t[v]) in[t[v]] = 1;
        }
    }
    for(int i = 0 ; i < tt ;i++){
        if(!in[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}