Cod sursa(job #2798460)

Utilizator Pop_MariaPop Maria Pop_Maria Data 11 noiembrie 2021 12:12:13
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

class Graf
{
private:

    int numar_noduri, numar_muchii, numar_componente = 0;
    vector <int> lista_adiacenta1[100001];
    vector <int> lista_adiacenta2[100001];
    vector <int> componenta[100001];
    vector <int> st;
    unordered_map <int, bool> vizitare1, vizitare2;

public:

    void citire();
    void parcurgere();
    void dfs1(int);
    void dfs2(int);
};

void Graf :: citire()
{
    int capat_stang, capat_drept;

    fin >> numar_noduri >> numar_muchii;

    for(int i = 1; i <= numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta1[capat_stang].push_back(capat_drept);
        lista_adiacenta2[capat_drept].push_back(capat_stang);
    }
}

void Graf :: dfs1(int nod)
{
    vizitare1[nod] = true;

    for(int i = 0; i < lista_adiacenta1[nod].size(); i++)
        if(!vizitare1[lista_adiacenta1[nod][i]])
            dfs1(lista_adiacenta1[nod][i]);

    st.push_back(nod);
}

void Graf :: dfs2(int nod)
{
    vizitare2[nod] = true;
    componenta[numar_componente].push_back(nod);

    for(int i = 0; i < lista_adiacenta2[nod].size(); i++)
        if(!vizitare2[lista_adiacenta2[nod][i]])
            dfs2(lista_adiacenta2[nod][i]);
}

void Graf :: parcurgere()
{
    for(int i = 1; i <= numar_noduri; i++)
        if(!vizitare1[i])
            dfs1(i);

    for(int i = st.size() - 1; i >= 0; i--)
        if(!vizitare2[st[i]])
    {
        dfs2(st[i]);
        numar_componente++;
    }

    fout << numar_componente << '\n';

    for(int i = 0; i < numar_componente; i++)
    {
        for(int j = 0; j < componenta[i].size(); j++)
            fout << componenta[i][j] << " ";

        fout << '\n';
    }
}

int main()
{
    Graf x;
    x.citire();
    x.parcurgere();

    fin.close();
    fout.close();

    return 0;
}