Cod sursa(job #1614294)

Utilizator jurjstyleJurj Andrei jurjstyle Data 25 februarie 2016 21:32:08
Problema Componente tare conexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>

using namespace std ;

ifstream f ("ctc.in") ;
ofstream g ("ctc.out") ;

int n , m ;
vector <int> G[100001] , GT[100001] ;
int Rez[100001] , VG[100001] , VGT[100001] ;

void Init ( int * v , int n )
{
 for ( int i = 1 ; i <= n ; ++i )
    v[i] = 0 ;
}
void DFS ( int nod )
{
 VG[nod] = 1 ;
 for ( vector <int> :: iterator I = G[nod].begin () ; I < G[nod].end() ; ++I )
        if ( !VG[*I] )
            DFS ( *I ) ;
}
void DFS_GT ( int nod )
{
 VGT[nod] = 1 ;
 for ( vector <int> :: iterator I = GT[nod].begin () ; I < GT[nod].end() ; ++I )
        if ( !VGT[*I] )
            DFS_GT ( *I ) ;
}
int main ()
{
 f >> n >> m  ;
 for ( int i = 1 ; i <= m ; ++i )
    {
     int x , y ;
     f >> x >> y ;
     G[x].push_back ( y ) ;
     GT[y].push_back ( x ) ;
    }
 int nr_componente = 0 ;
 for ( int i = 1 ; i <= n ; ++i )
    if ( Rez[i] == 0 )
        {
         nr_componente++ ;
         for ( int cnt = 1 ; cnt <= n ; ++cnt )
            VG[cnt] = VGT[cnt] = 0 ;
         DFS ( i ) ;
         DFS_GT ( i ) ;
         for ( int j = 1 ; j <= n ; ++j )
            if ( VG[j] * VGT[j] == 1 )
                Rez[j] = nr_componente ;
        }
 g << nr_componente ;
 return 0 ;
}