Cod sursa(job #2928621)

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

using namespace std;

    //declaram o variabila globala care sa contorizeze numarul variabilelor globale
    int n, nr_comp_conex;
    //construim un vector de vectori in care retinem nodurile pe care le contine fiecare componenta conexa
    vector <vector <int>> solutie;

    //vom folosi 2 liste de adiacenta, intrucat avem un graf orientat
    vector <vector <int>> ad_1; //lista adiacenta
    vector <vector <int>> ad_2; //lista adiacenta inversa

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

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

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

   //afisam nodurile pe care le contine fiecare componenta conexa
    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]);
        }
    }
    // introducem nodurile vizitate in dfs 1 intr-o stiva pentru a putea aplica apoi dfs 2
    st.push(nod);
}
void dfs_2(int nod)
{
      //intrucat nodul a fost vizitat in ambele dfs, vom atribui valoarea 2 in vectorul vizitat
    vizitat[nod] = 2;

    //vom adauga nodul in componenta conexa
    solutie[nr_comp_conex].push_back(nod);

    //parcurgem vecinii nodului curent. Daca acestia au fost vizitate in dfs_1, atunci apelam dfs_2
    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);



    //folosim un for pentru a citi muchiile din graf si construim  2 liste de adiacenta: cea propriu-zisa si cea inversa
    creare_lista(m);

    //parcurgem vectorul in care contorizam daca modurile au fost vizitate sau nu atat in dfs_1 cat si in dfs_2
    for(int i = 1; i <= n ; i++)
    {   //daca nodul nu a fost vizitat, atunci il marcam ca vizitat in dfs_1 si apoi apelam functia dfs_1
        if(vizitat[i] == 0)
        {
            vizitat[i]=1;
            dfs_1(i);
        }
    }

    //cat timp stiva contine elemente, atunci verificam daca acesta a fost vizitat in dfs_1 si apoi facem dfs_2(parc urgerea in ordine inversa)
    while(st.size() > 0)
    {
        nod = st.top();
        st.pop();
        if(vizitat[nod]==1)
        {
            nr_comp_conex++;
            dfs_2(nod);

        }
    }

    afisare();

    return 0;
}