Cod sursa(job #2795859)

Utilizator popaandaioanaPopa Anda-Ioana popaandaioana Data 7 noiembrie 2021 02:52:59
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

class graf_orientat
{
    int n, m; //n = nr. varfuri m = nr. arce
public:
    vector <int> lista[100001]; //in acest mod va fi stocat graful (lista adiacenta)
    vector <int> lista1[100001];
    stack <int> S;
    int contor;
    vector <int> ctc[100001];
    bool vizitate[100001];
    graf_orientat(int, int); //constructor
    void construire_graf_orientat_ctc();
    void refacere_viz();
    void dfs_1(int);
    void dfs_compTC(int);
};

graf_orientat :: graf_orientat(int n, int m)
{
    this -> n = n;
    this -> m = m;
}

void graf_orientat :: construire_graf_orientat_ctc()
{
    for(int i = 0; i < m; i ++) //parcurgem arcele
    {
        int u, v;
        in >> u >> v; //citim varfurile intre care exista arc
        lista[u].push_back(v); //lista[u] = varfurile unde se poate ajunge din u

        lista1[v].push_back(u); //lista1[v] = varfurile din care se poate ajunge in v
    }
}

void graf_orientat :: refacere_viz() //se marcheaza vectorul de vizitate cu 0
{
     for(int i = 1; i <= n; i ++)
        vizitate[i]=0;
}

void graf_orientat :: dfs_1(int nod) //parcurgere plecand din nod care este neviz.
{
    vizitate[nod] = 1; //marcheaza nodul ca vizitat
    for(int i = 0; i < lista[nod].size(); i ++) //parcurgem lista de vecini a lui nod
    {
        if(vizitate[lista[nod][i]] == 0) //daca vecinul i al lui nod nu a fost vizitat
        {
            dfs_1(lista[nod][i]); //apelam recursiv dfs pentru vecinul respectiv
        }
    }
     S.push(nod); //la intoarcerea din apelul recursiv, adaugam nodul in stiva
                    //in stiva se realizeaza un fel de sortare topologica, daca privim graful condensat, dpdv fiind aciclic
                    //(nodurile sunt grupate pe comp. tare conexe)
}

void graf_orientat :: dfs_compTC(int nod) //parcurgere plecand spre nod
{
    vizitate[nod] = 2;
    ctc[contor].push_back(nod); //pune nodul respectiv in vectorul rezultat si il marcheaza ca a fost vizitat de 2 ori
    for(int i = 0; i < lista1[nod].size(); i ++) //pt. fiecare nod i din care se poate ajunge in nod
    {
        if(vizitate[lista1[nod][i]] == 0) //daca nu a fost vizitat
        {
             dfs_compTC(lista1[nod][i]); //apelam recursiv pentru i
        }
    }
}

int main()
{
    int n, m;
    in >> n >> m; //se citesc nr. de noduri, nr. de muchii
    graf_orientat G(n, m); //se apeleaza constructorul
    G.construire_graf_orientat_ctc(); //se apeleaza functia de construire a grafului
    //CTC-Kosoraju
    //pune in stiva nodurile din parcurgerea dfs
    for(int j = 1; j <= n; j ++)
    {
        if(G.vizitate[j] == 0)
        {
            G.dfs_1(j);
        }
    }
    G.refacere_viz();
    while(!G.S.empty()) //daca stiva nu e goala
    {
        //scoate din stiva elemente pana cand gaseste unul neviz.
        int temp = G.S.top(); //salveaza top-ul stivei in temp
        G.S.pop(); //scoate primul elem. din stiva
        if(G.vizitate[temp] == 0) //daca nodul nu a fost viz. => el face parte dintr-o nou comp. tare conexa
        {
            G.contor++; //contorizam comp.
            G.dfs_compTC(temp); //generam comp. tare conexa prin parcurgere dfs in traspusa grafului
        }
    }
    out << G.contor << "\n";
    for(int i = 1; i <= G.contor; i ++)
    {
        for (int j = 0; j < G.ctc[i].size(); j ++)
        {
            out << G.ctc[i][j] << " ";
        }
        out<<"\n";
    }

}