Cod sursa(job #1038365)

Utilizator DiaconuDanDiaconu Dan DiaconuDan Data 21 noiembrie 2013 13:44:21
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
// v3
// - construiesc G graful original
// construiesc Gt graful transpus ( exista aceleasi arce dar cu sens schimbat )
// ambele prin liste de adiacenta
// pas1 : pt orice vf x din graf cafre nu se afla intr-o comp tare conexa

// fac dfs din x-> posordine(n) vf x va fi pus in vector dupa ce toti fii sai au fost deja pusi in graf

// pas 2 :

// parcurg vectorul postordine de la dreapta la stanga cu indice i= n, 1 si daca vf postordine[i] nu a fost vizitat
// in graful Gt atunci apelez DFST pentru post ordine[i]

#include <fstream>
#include <vector>

using namespace std;

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

int n , m, viz[108], preord[108], contor,nr, componente = 0 ;
vector <int> M[108], MT[108] , C[108] ;
int tari_con ;

void citire();
void dfs( int ) ;
void dfst( int ) ;
void afisare() ;

int main()
{
    citire();
    for ( int i = 1 ; i <= n ; i++)
        if ( viz[i] == 0 )
            dfs(i);
    for ( int i = n ; i >= 1 ; i--)
        if ( viz[ preord[i] ] == 1 )
        {
            componente++;
            dfst(preord[i]);
        }
    afisare();
    return 0;

}

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


void dfs(int k)
{
    viz[k] = 1 ;
    for ( int i = 0 ; i < M[k].size() ; i++)
        if ( viz[M[k][i]] == 0 )
            dfs(M[k][i]) ;
    preord[++contor] = k ;
}

void afisare()
{
    int i , j ;
    fout << componente << '\n' ;
    for  ( i = 1 ; i <= componente ; i++ )
    {
        for ( j = 0 ; j < C[i].size(); j++ )
            fout << C[i][j] << " " ;
        fout << '\n' ;
    }
}



void dfst(int k)
{

    viz[k] = 0 ;
    for ( int i = 0 ; i < MT[k].size() ; i++)
        if ( viz[MT[k][i]] == 1 )
            dfst(MT[k][i]) ;
    C[componente].push_back(k)  ;

}