Cod sursa(job #2928825)

Utilizator adamemi02emanuel adam adamemi02 Data 23 octombrie 2022 22:29:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <vector>
#include <fstream>
#include <stack>
#include<unordered_map>

using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n, componente_conexe;

vector <vector <int>> sol;

vector <vector <int>> lista_adiacenta;
vector <vector <int>> lista_adiacenta_transpus;
unordered_map <int,int> vizitare;
stack <int> stiva;

void dfs(int nod)
{
    for(int  i=0; i < lista_adiacenta[nod].size();i++)
    {
        if(vizitare[lista_adiacenta[nod][i]]==0)
        {
            vizitare[lista_adiacenta[nod][i]]=1;
            dfs(lista_adiacenta[nod][i]);
        }
    }
    /// introducem nodurile vizitate in dfs intr-o stiva pentru a putea aplica apoi dfs-ul transpus
    stiva.push(nod);
}
void dfs_transpus(int nod)
{
    ///daca nodul e vizitat in ambele  dfs-uri, marcam diferit vizitarea
    vizitare[nod] = -1;

    ///adaugam nodul in solutie
    sol[componente_conexe].push_back(nod);

    ///in caz de nodurile vecine au fost vizitate apelam dfs_transpus
    for( auto i = 0 ;i < lista_adiacenta_transpus[nod].size(); i++)
    {
        if(vizitare[lista_adiacenta_transpus[nod][i]] == 1)
        {
            dfs_transpus(lista_adiacenta_transpus[nod][i]);
        }
    }
}
int main()
{
    int n, m;
    cin>>n>>m;
    lista_adiacenta.resize(n+1);
    lista_adiacenta_transpus.resize(n+1);
    for(int i=1; i <= m ; i++)
    {   int a,b;
        cin>>a>>b;
        lista_adiacenta[a].push_back(b);
        lista_adiacenta_transpus[b].push_back(a);
    }

    sol.resize(n+1);


    for(int i = 1; i <= n ; i++)
    {
        if(vizitare[i] == 0)
        {
            vizitare[i]=1;
            dfs(i);
        }
    }
    ///cat timp avem elemente in stiva, verificam daca nodul a fost vizitat in dfs, iar apoi apelam dfs-ul transpus
    while(stiva.size() > 0)
    {
        int nod = stiva.top();
        stiva.pop();
        if(vizitare[nod]==1)
        {
            componente_conexe++;
            dfs_transpus(nod);

        }
    }

    cout<<componente_conexe<<"\n";

    ///afisarea
    for(int i=1; i <= componente_conexe ; i++)
    {
        for(auto nod: sol[i])
        {
            cout<< nod <<" ";
        }
        cout<<"\n";
    }

    return 0;
}