Pagini recente » Cod sursa (job #1397528) | Cod sursa (job #735815) | Cod sursa (job #386705) | Cod sursa (job #2444131) | Cod sursa (job #1614294)
#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 ;
}