Pagini recente » Atasamentele paginii Flooow | Atasamentele paginii Flooow | Profil Andrei_Icriverzi | Cod sursa (job #2821123) | Cod sursa (job #1563106)
#include <fstream>
#include <set>
using namespace std ;
ifstream f ("dfs.in") ;
ofstream g ("dfs.out") ;
set <int> G[100005] ;
bool vizitat[100005] ;
int N , M , nr ;
void citire () ;
void solve () ;
void dfs ( int ) ;
int main ()
{
citire () ;
solve () ;
f.close () ;
g.close () ;
return 0 ;
}
void citire ()
{
f >> N >> M ;
for ( int i = 1 ; i <= M ; ++i )
{
int x , y ;
f >> x >> y ;
G[x].insert ( y ) ;
G[y].insert ( x ) ;
}
}
void solve ()
{
for ( int i = 1 ; i <= N ; ++i )
if ( !vizitat[i] )
{
++nr ;
dfs ( i ) ;
}
g << nr ;
}
void dfs ( int nod )
{
vizitat[nod] = 1 ;
for ( set<int>::iterator I = G[nod].begin() ; I != G[nod].end() ; ++I )
if ( !vizitat[*I] )
dfs ( *I ) ;
}