Cod sursa(job #2175528)

Utilizator sebistetuCucolas Sebastian sebistetu Data 16 martie 2018 17:38:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include<fstream>
#include<list>
#include<bitset>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int Nmax = 100005;

list<int>Graf[Nmax], GrafT[Nmax], Sol[Nmax];
bitset<Nmax>Viz;
int Topologic[Nmax], NrElemTopologic, NrCompTC, NrNoduri, NrMuchii;

void Citire(){

    f >> NrNoduri >> NrMuchii;

    int nod1, nod2;
    for(int Index = 1; Index <= NrMuchii; ++Index){

        f >> nod1 >> nod2;
        Graf[nod1].push_back(nod2);
        GrafT[nod2].push_back(nod1);
    }
}

void SortareTopologica(int NodCurent){

    list<int>::iterator it;
    Viz[NodCurent] = true;

    for(it = Graf[NodCurent].begin(); it != Graf[NodCurent].end(); ++it)
        if(!Viz[*it])
            SortareTopologica(*it);

    Topologic[++NrElemTopologic] = NodCurent;
}

void ObtinereVectorSortTop(){

    int Index;
    for(Index = 1; Index <= NrNoduri; ++Index)
        if(!Viz[Index])
            SortareTopologica(Index);
}

void DFS(int NodCurent){

    list<int>::iterator it;
    Viz[NodCurent] = false;
    Sol[NrCompTC].push_back(NodCurent);

    for(it = GrafT[NodCurent].begin(); it != GrafT[NodCurent].end(); ++it)
        if(Viz[*it])
            DFS(*it);
}

void ObtinereCompTareConexe(){

    int Index;
    for(Index = NrElemTopologic; Index >= 1; --Index){

        if(Viz[Topologic[Index]]){

            ++NrCompTC;
            DFS(Topologic[Index]);
        }
    }
}

void Print(){

    g << NrCompTC << '\n';

    int Index;
    list<int>::iterator it;
    for(Index = 1; Index <= NrCompTC; ++Index){

        for(it = Sol[Index].begin(); it != Sol[Index].end(); ++it)
            g << *it << ' ';

        g << '\n';
    }
}

int main(){

    Citire();
    ObtinereVectorSortTop();
    ObtinereCompTareConexe();
    Print();
    return 0;
}