Cod sursa(job #1936813)

Utilizator robx12lnLinca Robert robx12ln Data 23 martie 2017 14:31:56
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include<fstream>
#include<vector>
#include<stack>
#define DIM 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y, low[DIM], niv[DIM], f[DIM], nr, cod;
vector<int> v[DIM], sol[DIM];
stack<int> st;
void dfs( int nod ){ //tarjan
    cod++;
    niv[nod] = low[nod] = cod; //consider nodu ca fiind propria componenta tare conexa
    st.push( nod );// adaug nodul in stiva
    f[nod] = 1;
    for( int i = 0; i < v[nod].size(); i++ ){
        int vecin = v[nod][i];
        //incerc sa vad daca nod nu cumva pot extinde componenta tare conexa a lui nod
        if( niv[vecin] == 0 ){
            dfs( vecin );
            low[nod] = min( low[nod], low[vecin] );
        }else{
            if( f[vecin] == 1 ){
                low[nod] = min( low[nod], low[vecin] );
            }
        }
    }
    if( low[nod] == niv[nod] ){ //insemna ca am format o componenta tare conexa din care face parte si nod
        // ea este formata din nodurile din stiva pana la nod
        nr++;
        while( st.top() != nod ){
            sol[nr].push_back( st.top() );
            f[ st.top() ] = 0; //definitizez componenta tare conexa
            st.pop();
        }
        sol[nr].push_back( st.top() );
        st.pop();
    }
    return;
}

int main(){
    fin >> n >> m;
    for( int i = 1; i <= m; i++ ){
        fin >> x >> y;
        v[x].push_back(y);
    }
    //niv[nod] = reprezinta o codificare unica a lui nodsi un vector de frecventa daca nod se afla deja intr-o componenta tare conexa
    //          cu cat este mai mic cu atat consider ca este mai aproape de radacina componentei tare conexe
    //          ( cel mai mic dintr- o  componenta repr radacina componentei )
    //low[nod] = reprezinta cel mai aropiat nod ( codul unic ) de radacina componentei tare conexe din care face parte
    //f[nod] = 0 daca consider ca e intr-o componenta tare conexa definitizata si 1 pt una in curs de definire
    cod = 0;
    for( int i = 1; i <= n; i++ ){
        if( niv[i] == 0 ){
            dfs(i);
        }
    }
    fout << nr << "\n";
    for( int i = 1; i <= nr; i++ ){
        for( int j = 0; j < sol[i].size(); j++ ){
            fout << sol[i][j] << " ";
        }
        fout << "\n";
    }
    return 0;
}