Cod sursa(job #2969883)

Utilizator GeorgeNistorNistor Gheorghe GeorgeNistor Data 23 ianuarie 2023 20:45:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

int V, E;
vector<vector<int>> adjList, adjListTrans;
vector<bool> visited;
stack<int> stk;

void init(){
    adjList.resize(V+1);
    adjListTrans.resize(V+1);
    visited.resize(V+1);
}

void read() {
    in >> V >> E;
    init();
    for(int i = 0; i < E; i++){
        int u, v;
        in >> u >> v;
        adjList[u].push_back(v);
        adjListTrans[v].push_back(u);
    }
}

void print(const vector<vector<int>>& SCCs){
    out << SCCs.size() << '\n';
    for(const auto & scc: SCCs){
        for(auto u: scc)
            out << u << ' ';
        out << '\n';
    }
}

void first_dfs(int u){
    visited[u] = true;
    for(auto v: adjList[u]){
        if(!visited[v])
            first_dfs(v);
    }
    stk.push(u);
}

void second_dfs(int u, vector<int>& scc){
    visited[u] = true;
    scc.push_back(u);
    for(auto v: adjListTrans[u]){
        if(!visited[v])
            second_dfs(v, scc);
    }
}

void kosaraju(){
    for(int i = 1; i <= V; i++){
        if(!visited[i])
            first_dfs(i);
    }
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> SCCs; // Strongly Connected Components
    while(!stk.empty()){
        int u = stk.top();
        stk.pop();
        if(!visited[u]){
            vector<int> scc = {};
            second_dfs(u, scc);
            SCCs.push_back(scc);
        }
    }
    print(SCCs);
}

int main() {
    read();
    kosaraju();
    return 0;
}