Cod sursa(job #2929504)

Utilizator elenaa_g23Elena Georgescu elenaa_g23 Data 25 octombrie 2022 23:29:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

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

int nrn,nrm,i,j,x,y,nrc=0;
vector<vector<int>> lista_adiacenta, lista_t;
vector<int> vizitat;
vector<vector<int>> cmpCon;
stack<int> stiva;

void componente_afisare(){
    for(i=1;i<=nrc;i++)
        {
        for(int x : cmpCon[i])
            g<<x<<' ';
        g<<'\n';
    }
}

void dfs1(int nod)
{
    vizitat[nod] = 1;
    for(int x : lista_adiacenta[nod])
        if(!vizitat[x])
            dfs1(x);

    stiva.push(nod);
}

void dfs2(int nod)
{
    vizitat[nod]=1;

    for(int x : lista_t[nod])
        if(!vizitat[x])
            dfs2(x);

    cmpCon[nrc].push_back(nod);
}

int main()
{

    f>>nrn>>nrm;
    lista_adiacenta.resize(nrn+1);
    lista_t.resize(nrn+1);
    vizitat.resize(nrn+1, 0);
    cmpCon.resize(nrn+1);
    for(i=1;i<=nrm;i++)
    {
        f>>x>>y;
        lista_adiacenta[x].push_back(y);
        lista_t[y].push_back(x);
    }

    for(i=1;i<=nrn;i++)
        if(!vizitat[i])
            dfs1(i);

    fill(vizitat.begin(), vizitat.end(), 0);
    nrc = 0;

    while(stiva.empty()==0)
    {
        int curr = stiva.top();
        stiva.pop();

        if(!vizitat[curr])
        {
            nrc++;
            dfs2(curr);
        }

    }

    g<<nrc<<'\n';
    componente_afisare();

    return 0;
}