Cod sursa(job #2668555)

Utilizator SahisttulArsene Marinel Sahisttul Data 5 noiembrie 2020 00:26:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int const NMAX = 100001;

int n, m, nr_comp_tare_conexe, viz[NMAX];
vector<int> arce[100001], arceTranspusa[NMAX];
stack<int> stiva;                                     ///folosim o stiva pentru a retine parcurgerea grafului si pt a adauga recursiv elementele in aceasta
vector<int> componenteTareConexe[NMAX];               ///vector pentru componentele tare conexe

void citire()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        arce[x].push_back(y);                  ///inseram in lista de arce
        arceTranspusa[y].push_back(x);         ///inseram arcul cu directie opusa in lista de arce transpuse
    }
}

void DFS(int nod)
{
    viz[nod] = 1;
    for(int i = 0; i < arce[nod].size(); i++)
    {
        int vecin = arce[nod][i];
        if(viz[vecin] == 0)
            DFS(vecin);
    }
    stiva.push(nod);      ///salvam pe stiva ordinea nodurilor
}

void DFS_transpus(int nod)
{
    viz[nod] = 2;                 ///marcam cu 2 a doua parcurgere a unui nod din graful transpus
    componenteTareConexe[nr_comp_tare_conexe].push_back(nod); ///adaugam nodul in lista de componente tare conexe
    for(int i = 0; i < arceTranspusa[nod].size(); i++)
    {
        int vecin = arceTranspusa[nod][i];
        if(viz[vecin] == 1)             ///verificam daca vecinul a fost vizitat in prima parcurgere dfs
            DFS_transpus(vecin);
    }
}

void afis()
{
    g << nr_comp_tare_conexe << '\n';
    for(int i = 1; i <= nr_comp_tare_conexe; i++)
    {
        for(int j = 0; j < componenteTareConexe[i].size(); j++)
            g << componenteTareConexe[i][j] << ' ';
        g << '\n';
    }
}

int main()
{
    citire();
    //
    for(int i = 1; i <= n; i++)
        if(viz[i] == 0)
            DFS(i);
    //
    while(!stiva.empty())
    {
        int nod_curent = stiva.top();       ///luam nodul curent din varful stivei
        if(viz[nod_curent] == 1)
        {
            nr_comp_tare_conexe++;
            DFS_transpus(nod_curent);
        }
        stiva.pop();
    }
    //
    afis();
    return 0;
}