Cod sursa(job #2666928)

Utilizator ADRIAN.CATRINOIUAdrian Catrinoiu ADRIAN.CATRINOIU Data 2 noiembrie 2020 16:52:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int vizitat[100001], nrCompTareConexe;                         //un vector de muchii vizitate
vector<int> listaMuchii[100001], listaMuchiiTranspusa[100001]; //vector pentru lista de muchii si lista de muchii transpuse
vector<int> componenteTareConexe[100005];                      //vector pentru componentele tare conexe
stack<int> stiva;                                              // folosim o stiva pentru a retine parcurgerea grafului si pt a adauga recursiv elementele in aceasta
void dfs(int nod)
{
    int vecin;
    vizitat[nod] = 1; //marcam cu 1 prima parcurgere in adancime a fiecarui nod

    for (int i = 0; i < listaMuchii[nod].size(); i++)
    {
        vecin = listaMuchii[nod][i];
        if (!vizitat[vecin])
            dfs(vecin);
    }
    stiva.push(nod);
}
void dfs_transpus(int nod)
{
    int vecin;
    vizitat[nod] = 2;                                      //marcam cu 2 a doua parcurgere a unui nod din graful transpus
    componenteTareConexe[nrCompTareConexe].push_back(nod); //adaugam in lista de componente tare conexe nodul in lista in care apartine
    for (int i = 0; i < listaMuchiiTranspusa[nod].size(); i++)
    {
        vecin = listaMuchiiTranspusa[nod][i];
        //verificam daca vecinul a fost vizitat in prima parcurgere de dfs
        if (vizitat[vecin] == 1)
            dfs_transpus(vecin);
    }
}
int main()
{
    int x, y, i, noduri, muchii, nodCurent;
    fin >> noduri >> muchii;
    //facem lista de muchii/adiacenta ale grafului
    for (i = 1; i <= muchii; i++)
    {
        fin >> x >> y;
        listaMuchii[x].push_back(y);          //inseram in lista de muchii
        listaMuchiiTranspusa[y].push_back(x); //inseram muchia cu directie opus in lista de muchii transpuse
    }
    //parcurgem graful in adancime pentru a stabili ordinea nodurilor si pentru a umple stiva
    for (i = 1; i <= noduri; i++)
    {
        if (vizitat[i] == 0)
            dfs(i);
    }

    while (!stiva.empty())
    {
        //nodul curent va fi ultimul element introdus din stiva
        nodCurent = stiva.top();
        //daca a fost vizitat in prima parcurgere cu dfs vom mari numarul de componente tari conexe si
        //le vom cauta si pe restul din aceeasi componenta tare conexa
        if (vizitat[nodCurent] == 1)
        {
            nrCompTareConexe++;
            dfs_transpus(nodCurent);
        }
        stiva.pop();
    }
    fout << nrCompTareConexe << '\n';
    for (i = 1; i <= nrCompTareConexe; i++)
    {
        for (int j = 0; j < componenteTareConexe[i].size(); j++)
        {
            fout << componenteTareConexe[i][j] << " ";
        }
        fout << '\n';
    }
    return 0;
}