Pagini recente » Cod sursa (job #170404) | Cod sursa (job #1310763) | Cod sursa (job #552524) | Cod sursa (job #597772) | Cod sursa (job #1038370)
// 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 >= 0 ; 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) ;
}