lixoo_tarjan

vector<ii> adj[MAXV];
int dfs_num[MAXV], dfs_low[MAXV], vis[MAXV];
int dfsNumber, numSCC, V;
vector<int> S;

void tarjan(int u) {

    dfs_low[u] = dfs_num[u] = dfsNumber++;
    S.pb(u);
    vis[u] = 1;
    int tam = adj[u].size();
    rep(j,0,tam){
         ii v = adj[u][j];
         if (dfs_num[v.first] == -1)
             tarjan(v.first);
         if (vis[v.first])
             dfs_low[u] = min(dfs_low[u], dfs_low[v.first]);
    }

    if (dfs_low[u] == dfs_num[u]) {
        ++numSCC;  // componente numero (numSCC)
        while (1) {
             int v = S.back(); S.pop_back(); vis[v] = 0;
            // v = vertices da componente atual(numSCC)
             if (u == v) break;
        }
    }
}


int main(){

    V = 4;

    rep(i,0,V+1){
        dfs_low[i] = vis[i] = 0;
        dfs_num[i] = -1;
    }

    dfsNumber = numSCC = 0;

    rep(i,0,V)
        if (dfs_num[i] == -1)
            tarjan(i);

    printf("Qtdade de SCC -> %d\n",numSCC);

    return 0;
}