Cod sursa(job #2338284)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 7 februarie 2019 11:39:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#define NMax 100005
using namespace std;

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

stack < int > myStack;
vector<int> G[NMax],GT[NMax],CTC[NMax];
int N,M,NrCTC,Use[NMax],O[NMax],k;

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(unsigned int i=0; i<G[Nod].size();i++)
    {
        int Vecin = G[Nod][i];
        if(!Use[Vecin])
            DFSP(Vecin);
    }
    myStack.push(Nod);
}

void DFSM(int Nod)
{
    Use[Nod] = 2; CTC[NrCTC].push_back(Nod);
    for(unsigned int i=0; i<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);
    
    while(!myStack.empty()) {
        int Nod = myStack.top();
        if (Use[Nod] == 1) {
            NrCTC++;
            DFSM(Nod);
        }
        myStack.pop();
    }
}

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

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