Cod sursa(job #2798586)

Utilizator linte_robertLinte Robert linte_robert Data 11 noiembrie 2021 16:31:44
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

void dfs( int k, vector < vector < int > > &vecini, vector < int > &culoare, vector < int > &s ){
    culoare[k] = 1;
    for( int i = 0; i < vecini[k].size(); i++ ){
        if( culoare[ vecini[k][i] ] == 0 ){
            dfs( vecini[k][i], vecini, culoare, s );
        }
    }
    s.push_back(k);
}
void dfsT( int k, vector < vector < int > > &vecini, vector < int > &culoare, vector < int > & graf){
    culoare[k] = 1;
    graf.push_back(k);
    for( int i = 0; i < vecini[k].size(); i++ ){
        if( culoare[ vecini[k][i] ] == 0 ){
            dfsT( vecini[k][i], vecini, culoare, graf );
        }
    }
}

int main(){
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    vector < vector < int > > vecini;
    vector < vector < int > > transpus;
    vector < int > culoare;
    vector < int > s;
    int nr_noduri, nr_muchii;
    fin >> nr_noduri >> nr_muchii;
    for(int i = 0; i <= nr_noduri; i++){
        vector < int > v;
        vecini.push_back(v);
        transpus.push_back(v);
    }
    for( int i = 0; i < nr_muchii; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        vecini[intrare].push_back(iesire);
        transpus[iesire].push_back(intrare);
    }
    for( int i = 0; i <= nr_noduri; i++ ){
        culoare.push_back(0);
    }
    for( int i = 1; i <= nr_noduri; i++ ){
        if( culoare[i] == 0 ){
            dfs(i, vecini, culoare, s);
        }
    }
    int contor = 0;
    vector < vector < int > > grafuri;
    for( int i = s.size() - 1; i >= 0; i-- ){
        if( culoare[ s[i] ] == 0 ){
            contor++;
            vector < int > graf;
            dfsT( s[i] , transpus, culoare, graf);
            grafuri.push_back(graf);
        }
    }
    fout << contor << endl;
    for( int i = 0; i < grafuri.size(); i++ ){
        for( int j = 0; j < grafuri[i].size(); j++ ){
            fout << grafuri[i][j] << " ";
        }
        fout << '\n';
    }
}