Cod sursa(job #2797123)

Utilizator iustin.pericicaPericica Iustin iustin.pericica Data 9 noiembrie 2021 11:59:19
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#define VALMAX 100005

using namespace std;

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


vector<int> componente[VALMAX+1];


stack <int> Stiva;
int vizitat[VALMAX + 1];
int vizitatT[VALMAX + 1];

struct nod{

nod *next;
int val;

};

class OrientedGraph{

protected:
    nod *varfuri[VALMAX];
    nod *varfuriT[VALMAX];
    int nrVarfuri;
    int nrMuchii;
    int varfStart;

public:
    OrientedGraph(){
        vizitAll();
        //makeDrc0();
    }

    OrientedGraph(int nrV, int nrM): nrVarfuri(nrV), nrMuchii(nrM){
        vizitAll();
        //makeDrc0();
    }

void vizitAll(){
    /*
    for(int i = 1;i<=VALMAX;++i){
        vizitat[i] = 0;
        vizitatT[i] = 0;
    }
    */
}


void citireOrientat(){
    if(!nrVarfuri)fin>>nrVarfuri>>nrMuchii;
/// default behavior
    for(int i = 1;i<=nrMuchii;++i){
        int x, y;
        fin>>x>>y;
        nod *p = new nod;
        p->val = y;
        p->next = varfuri[x];
        varfuri[x] = p;

        p = new nod;
        p->val = x;
        p->next = varfuriT[y];
        varfuriT[y] = p;

    }
}

void afisare(){

    for(int i = 1;i<=nrVarfuri;++i){
        nod *p = varfuri[i];
        cout<<"varf: "<<i<<"...: ";
        while(p){
            cout<<p->val<<" ";
            p = p->next;
        }
        cout<<endl;
    }

}


};

class ComponenteTareConexe: public OrientedGraph{

public:
    ComponenteTareConexe(): OrientedGraph(){}
    ComponenteTareConexe(int nrV, int nrM): OrientedGraph(nrV, nrM){}


void dfs1(int varf){

    vizitat[varf] = 1;
    nod *p = varfuri[varf];
    while(p){
        if(!vizitat[p->val]){
            dfs1(p->val);
        }
        p = p->next;
    }
    Stiva.push(varf);

}

void dfs2(int varf, int contorComp){

vizitatT[varf] = 1;
nod *p = varfuriT[varf];
componente[contorComp].push_back(varf);

while(p){
    if(!vizitatT[p->val]){
        dfs2(p->val, contorComp);
    }
    p = p->next;
}

}

void parcurgere(){
    for(int i = 1;i<=nrVarfuri;++i){
        if(!vizitat[i]){
            dfs1(i);
        }
    }

}

void componenteTare(){

    int contorComp = 0;
    while(!Stiva.empty()){

        int varf = Stiva.top();
        Stiva.pop(); /// nu l mai folosim
        if(!vizitatT[varf]){
            contorComp++;
            dfs2(varf, contorComp);
        }
    }

    fout<<contorComp<<endl;
    for(int i = 1;i<=contorComp;++i){
        int lungime = componente[i].size();
        for(int j = 0;j<lungime;++j){
            fout<<componente[i][j]<<" ";
        }
        fout<<endl;
    }


}

};


int main()
{

    ComponenteTareConexe g;
    g.citireOrientat();
    //g.afisare();
    g.parcurgere();
    g.componenteTare();

    return 0;
}