Strongly connected components

dfs.cpp

int used[N];
bool cycle;
vector<int> order;
vector<int> comp[N];
vector<int> G[N], G2[N];

void dfs(int v){
    used[v] = 1;
    for(int i = 0; i < (int) G[v].size(); i++){
        int to = G[v][i];
        if(!used[to]) dfs(to);
    }
    order.push_back(v);
}


void dfs2(int v, int num){
    used[v] = 2;
    comp[num].push_back(v);
    for(int i = 0; i < (int) G2[v].size(); i++){
        int to = G2[v][i];
        if(used[to] != 2) dfs2(to, num);
    }
}

int main(){
    for(int i = 0; i < m; i++){
        cin >> v1 >> v2;
        G[v1].push_back(v2);    
        G2[v2].push_back(v1);   // here we compute the transpose of G, 
    }
    for(int i = 1; i <= n; i++){
        if(!used[i]){
            dfs(i);
        }
    }
    int num = 0;
    reverse(order.begin(), order.end());
    for(int i = 0; i < n; i++){
        int v = order[i];
        if(used[v] == 2) continue;
        
        
        dfs2(v, num++);
    }
}