Cod sursa(job #1613955)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 25 februarie 2016 18:42:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMax = 100005;

int N,M,NRCTC;
int Use[NMax],X[NMax],k;

vector <int> G[NMax],GT[NMax];
vector <int> CTC[NMax];

void Read()
{
    fin>>N>>M;
    for(int i = 1; i<= M; ++i)
        {
            int x,y;
            fin>>x>>y;
            G[x].push_back(y);
            GT[y].push_back(x);
        }
}

void DFSP(int Nod)
{
    Use[Nod] = 1;
    for(int i = 0; i < (int)G[Nod].size(); i++)
        {
            int Vecin = G[Nod][i];
            if(!Use[Vecin])
                DFSP(Vecin);
        }
    X[++k] = Nod;
}

void DFSM(int Nod)
{
    Use[Nod] = 0;
    CTC[NRCTC].push_back(Nod);

    for(int i = 0; i < (int)GT[Nod].size(); i++)
        {
            int Vecin = GT[Nod][i];
            if(Use[Vecin]==1)
                DFSM(Vecin);
        }
}

void Solve()
{
    for(int i = 1; i <= N; i++)
        if(!Use[i])
            DFSP(i);

    for(int i = N; i >= 1; i--)
        {
            if(Use[X[i]]==1)
                {
                    NRCTC++;
                    DFSM(X[i]);
                }
        }
}

void Print()
{
    fout<<NRCTC<<"\n";

    for(int i = 1; i<=NRCTC; i++)
        {
        for(int j = 0; j < (int)CTC[i].size(); j++)
            fout<<CTC[i][j]<<" ";
        fout<<"\n";
        }
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}