Cod sursa(job #2798725)

Utilizator CalinCruceanu3576Cruceanu CalinCruceanu3576 Data 11 noiembrie 2021 19:32:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
 
class Graf {

private:

    int N;                                        
    vector< vector<int> > adc, adc2;
    vector<int> viz, sortate;
    
    void DfsSortare(int nod);
    void DfsTareConexe(int node, vector<int> &a);

public:

    Graf( int n );
    void AdaugaMuchie( int x, int y);
    vector<int>Sortare();
    void CompTareConexe();

};

void Graf :: DfsSortare(int nod) {
    int i, w;
    viz[nod] = 1;
	
    for(i = 0; i < adc[nod].size(); i++) {
        w = adc[nod][i];
        if(viz[w] == 0)
			DfsSortare(w);
    }
    sortate.push_back(nod);
}

void Graf :: DfsTareConexe(int nod, vector<int> &a) {
    viz[nod] = 1;
    for(int i = 0; i < adc2[nod].size(); i++) {
        int w = adc2[nod][i];
        if( viz[w] == 0 )
            DfsTareConexe(w, a);
    }
    a.push_back(nod);
}
 
Graf :: Graf(int n) {
    N = n;
    adc.resize(n + 1);
    adc2.resize(n + 1);
    viz.resize(n + 1);
}

void Graf :: AdaugaMuchie(int x, int y) {
    adc[x].push_back(y);
    adc2[y].push_back(x);
}

vector<int> Graf :: Sortare() {
    for( int i = 1; i <= N; i++ )
        viz[i] = 0;
    for( int i = 1; i <= N; i++ )
        if( viz[i] == 0 )
            DfsSortare(i);
    return sortate;
}

void Graf :: CompTareConexe() {
    vector<vector<int> > a;
    vector<int> v_sortat = Sortare();
    int curr, i, j;
    for(i = 0; i <= N; i++)
        viz[i] = 0;
    for(i = v_sortat.size() - 1; i >= 0; i--) {
        vector<int> ctc;
        curr = v_sortat[i];
        if(viz[curr]) continue;
        DfsTareConexe(curr, ctc);
        a.push_back(ctc);
    }
    fout<<a.size()<<"\n";
    for(i = 0 ; i < a.size(); i++){
        for(j = 0; j < a[i].size(); j++)
            fout<<a[i][j]<<" ";
        fout<<"\n";
    }
}

int main()
{
    int i, n, m, x, y;
    fin >> n >> m;
    Graf G(n);
    for(i = 1; i <= m; i++) {
        fin>>x>>y;
        G.AdaugaMuchie(x, y);
    }
    G.CompTareConexe();
    return 0;
}