Cod sursa(job #2928405)

Utilizator Andreeamiruna27Mindrescu Andreea Andreeamiruna27 Data 22 octombrie 2022 21:11:06
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <vector <int>> lista_adiacenta;
vector <vector <int>> lista_adiacenta_transpusa;
vector <vector <int>> solutie;
vector <int> stiva;
vector <int> nivel;


void dfs(int a)
{
    int j;
    for(long unsigned j=0; j<lista_adiacenta[a].size(); j++)
    {
        if(nivel[lista_adiacenta[a][j]]==0)
        {
            nivel[lista_adiacenta[a][j]]=1;
            dfs(lista_adiacenta[a][j]);
        }
    }

    stiva.push_back(a);
}



void dfs_transpus(int a)
{
    int j;
    solutie[nrcomponente].push_back(a);
    nivel[a]=2;
    for(long unsigned j=0; j<lista_adiacenta_transpusa[a].size(); j++)
    {
        if(nivel[lista_adiacenta_transpusa[a][j]]==1)
        {
            dfs_t(lista_adiacenta_transpusa[a][j]);
        }
    }
}
int main()
{
    int a, b, noduri, muchii ,nod, i;
    f>>noduri>>muchii;
    lista_adiacenta.resize(noduri+1);
    lista_adiacenta_transpusa.resize(noduri+1);
    nivel.resize(noduri+1);
    solutie.resize(noduri+1);
    for(i=0; i<muchii; i++)
    {
        f>>a>>b;
        lista_adiacenta[a].push_back(b);
        lista_adiacenta_transpusa[b].push_back(a);
    }
    for(i=1; i<=noduri; i++)
    {   nivel[i]=0;
    }

    for(i=1; i<=noduri; i++)
    {
        if(nivel[i]==0)
        {
            nivel[i]=1;
            dfs(i);
        }
    }

    while(!stiva.empty())
    {
        nod=stiva.back();
        stiva.pop_back();
        if(nivel[nod]==1)
        {
            nrcomponente++;
            dfs_transpust(nod);
        }
    }
    g<<nrcomponente<<endl;
    for(i=1; i<=nrcomponente; i++)
    {
        for(long unsigned int j=0; j<solutie[i].size(); j++)
        {
            g<<solutie[i][j]<<" ";
        }
        g<<endl;
    }
    return 0;
}