Cod sursa(job #3002727)

Utilizator Vali_nnnValentin Nimigean Vali_nnn Data 15 martie 2023 02:03:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");



vector <int> gr[200000] , gt[200000];

int top[200000] , in , n , m , x , y;
bool viz[200000];

vector <vector<int> >ctc;
vector <int> aux;

void dfs( int x ){

    viz[x] = 1;

    for(int i=0 ;i<gr[x].size();i ++){
int it=gr[x][i];
if(!viz[it]){
            dfs(it);
        }
    }

    top[in--] = x;
}

void dfst( int x ){

    viz[x] = 0;

    aux.push_back(x);

    for(int i=0 ;i<gt[x].size();i++){
            int it=gt[x][i];
        if(viz[it]){
            dfst(it);
        }
    }
}

int main(){

 f >> n >> m;

    in = n;

    for(int j=1;j<=m;j++)
        {
f>> x >> y;

        gr[x].push_back(y);
        gt[y].push_back(x);
    }

    for(int i = 1 ; i <= n ; i++){

        if(!viz[i]) dfs(i);
    }

    for(int i = 1 ; i <= n ; i++){

        if(viz[top[i]]){

            aux.clear();

            dfst(top[i]);

            ctc.push_back(aux);

        }
    }
g<< ctc.size() << '\n';

for(int j=0;j<ctc.size();j++)
 {for(int k=0;k<ctc[j].size();k++)
g<<ctc[j][k]<<" ";
g<<'\n';

}
    return 0;
}