Cod sursa(job #2928623)

Utilizator CosminaBuruianaCosmina Buruiana CosminaBuruiana Data 23 octombrie 2022 15:21:59
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>

using namespace std;


    int n, nr_comp_conex;

    vector <vector <int>> solutie;


    vector <vector <int>> ad_1;
    vector <vector <int>> ad_2;

    vector <int> vizitat;
    stack <int> st;

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

void afisare()
{
    g<<nr_comp_conex<<"\n";


    for( long long int i=1; i <= nr_comp_conex ; i++)
    {
        for(auto v: solutie[i])
        {
            g<< v <<" ";
        }
        g<<"\n";
    }
}

void dfs_1(int nod)
{
    for(auto i=0; i < ad_1[nod].size();i++)
    {
        if(vizitat[ad_1[nod][i]]==0)
        {
            vizitat[ad_1[nod][i]]=1;
            dfs_1(ad_1[nod][i]);
        }
    }

    st.push(nod);
}
void dfs_2(int nod)
{

    vizitat[nod] = 2;


    solutie[nr_comp_conex].push_back(nod);

    for( auto i = 0 ;i < ad_2[nod].size(); i++)
    {
        if(vizitat[ad_2[nod][i]] == 1)
        {
            dfs_2(ad_2[nod][i]);
        }
    }
}

creare_lista(int m)
{
    for(int i=1;i <= m ; i++)
    {   int a,b;
        f>>a>>b;
        ad_1[a].push_back(b);
        ad_2[b].push_back(a);
    }

}
int main()
{
    int m,nod,i;
    f>>n>>m;

    solutie.resize(n+1);
    vizitat.resize(n+1,0);
    ad_1.resize(n+1);
    ad_2.resize(n+1);




    creare_lista(m);


    for(int i = 1; i <= n ; i++)
    {
        if(vizitat[i] == 0)
        {
            vizitat[i]=1;
            dfs_1(i);
        }
    }


    while(st.size() > 0)
    {
        nod = st.top();
        st.pop();
        if(vizitat[nod]==1)
        {
            nr_comp_conex++;
            dfs_2(nod);

        }
    }

    afisare();

    return 0;
}