Cod sursa(job #1092266)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 26 ianuarie 2014 19:51:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
//Componente tare conexe - O(N+M)
#include<fstream>
#include<bitset>
#include<vector>
#define Nmax 100099
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int N,M,sol,TSort[Nmax];

vector < int > Graph[Nmax],Transpus[Nmax],Comp[Nmax];
bitset < Nmax > viz;

void DFS(int nod)
{
    viz[nod]=1;
    vector < int > :: iterator it;
    for(it=Graph[nod].begin(); it!=Graph[nod].end(); ++it)
        if(!viz[*it])DFS(*it);
    TSort[++TSort[0]]=nod;
}
void DFST(int nod)
{
    viz[nod]=0;
    Comp[sol].push_back(nod);
    vector < int > :: iterator it;
    for(it=Transpus[nod].begin(); it!=Transpus[nod].end(); ++it)
        if(viz[*it])DFST(*it);

}

void Tarjan()
{
    for(int i=1;i<=N;++i)
        if(!viz[i]) DFS(i);
    for(int i=N;i>=1;--i)
        if(viz[TSort[i]])
        {
            ++sol;
            DFST(TSort[i]);
        }
}

void ReadInput(),PrintOutPut();
int main()
{
    ReadInput();
    Tarjan();
    PrintOutPut();
    return 0;
}


void ReadInput()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
        {
            int x,y;
            f>>x>>y;
            Graph[x].push_back(y);
            Transpus[y].push_back(x);
        }
}

void PrintOutPut()
{
    g<<sol<<'\n';
    for(int i=1;i<=sol;++i,g<<'\n')
        for(int j=0;j<Comp[i].size();++j)g<<Comp[i][j]<<' ';
    f.close();g.close();
}