Cod sursa(job #1069109)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 29 decembrie 2013 14:18:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<bitset>
#include<vector>
#define Nmax 100099
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int N,M,X,Y,i,Cnt,TSort[Nmax],T;

vector < int > G[Nmax],GT[Nmax],Sol[Nmax];
bitset < Nmax > viz;

void DFS(int nod)
{
    vector < int > :: iterator it;
    for(it=G[nod].begin();it!=G[nod].end();++it)
        if(!viz[*it])
        {
            viz[*it]=1;
            DFS(*it);
        }
    TSort[++T]=nod;
}
void DFST(int nod)
{
    Sol[Cnt].push_back(nod);
    vector < int > :: iterator it;
    for(it=GT[nod].begin();it!=GT[nod].end();++it)
        if(viz[*it])
        {
            viz[*it]=0;
            DFST(*it);
        }
}
int main()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
        {
            int x,y;
            f>>x>>y;
            G[x].push_back(y);
            GT[y].push_back(x);
        }
    for(int i=1;i<=N;++i)
        if(!viz[i]) {viz[i]=1; DFS(i);}
    for(int i=N;i>=1;--i)
        if(viz[TSort[i]])
        {
            ++Cnt;
            viz[TSort[i]]=0;
            DFST(TSort[i]);
        }
    g<<Cnt<<'\n';
    for(int i=1;i<=Cnt;++i,g<<'\n')
        for(int j=0;j<Sol[i].size();++j)g<<Sol[i][j]<<' ';
    f.close();g.close();
    return 0;
}