Cod sursa(job #2346602)

Utilizator Robys01Robert Sorete Robys01 Data 17 februarie 2019 20:46:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;

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

vector <int> A[NMAX], AT[NMAX], Mat[NMAX], postordine;
int n, m, nr;
bool viz[NMAX];

void citire(){
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y; fin>>x>>y;
        A[x].push_back(y);
        AT[y].push_back(x);
    }

}

void DFS(int x){
    viz[x] = true;
    for(size_t i = 0; i<A[x].size(); i++)
        if(!viz[A[x][i]])
            DFS(A[x][i]);
    postordine.push_back(x);

}
void DFST(int x){
    viz[x] = false;
    Mat[nr].push_back(x);
    for(size_t i = 0; i<AT[x].size(); i++){
        if(viz[AT[x][i]])
            DFST(AT[x][i]);
    }
}


int main(){
    citire();
    for(int i=1; i<=n; i++){
        if(!viz[i])
            DFS(i);
    }

    for(int i=postordine.size()-1; i>=0; i--){
        if(viz[postordine[i]]){
            nr++;
            DFST(postordine[i]);
        }
    }
    fout<<nr<<'\n';
    for(int i=1; i<=nr; i++){
        for(size_t j = 0; j<Mat[i].size(); j++)
            fout<<Mat[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}