Cod sursa(job #1613888)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 25 februarie 2016 18:08:20
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 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];

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);
        }
}

void DFSM(int Nod)
{
    Use[Nod] = 2;
    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);
                    NRCTC++;
                    DFSM(i);
                    for(int i = 1; i<=N; i++)
                        if(Use[i]==1)
                            Use[i] = 0;
                }
        }
}

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;
}