Cod sursa(job #2928543)

Utilizator biancar28Radulescu Alexia-Bianca biancar28 Data 23 octombrie 2022 12:22:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

//Algoritmul lui Kosoraju

vector<vector<int>>lista;
vector<int>viz;
vector<vector<int>>transpusa;
stack<int>stiva;
vector<vector<int>>conexe;
int count;

void dfs(int nod){
    viz[nod]=1;
    for(auto & i:lista[nod]){
        if(!viz[i]){
            dfs(i);
        }
    }
    stiva.push(nod);
}

void dfst(int nod){
    viz[nod]=2;
    conexe[count-1].push_back(nod);
    for(auto & i:transpusa[nod]){
        if(viz[i]!=2){
            dfst(i);
        }
    }
}

int main() {
    int n,m,x,y,nod;
    f>>n>>m;
    lista.resize(n+1);
    viz.resize(n+1,0);
    transpusa.resize(n+1);
    conexe.resize(n+1);

    //creez lista de adiacenta
    while(f){
        f>>x>>y;
        lista[x].push_back(y);

    }

    //parcurg graf prin dfs
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            dfs(i);
        }
    }

    //creez transpusa listei de adiacenta
    for(int i=1;i<=n;i++){
        for(auto & j:lista[i]){
            transpusa[j].push_back(i);
        }
    }

    //parcurg stiva si fac dfs pe transpusa listei de adiacenta
    while(!stiva.empty()){
        nod=stiva.top();
        stiva.pop();
        if(viz[nod]==1){
            count++;
            dfst(nod);
        }
    }
    g<<count<<"\n";
    for(int i=0;i<count;i++){
        for(auto & z:conexe[i]){
            g<<z<<" ";
        }
        g<<"\n";
    }

    return 0;
}