Pagini recente » Borderou de evaluare (job #2046394) | Cod sursa (job #1031242) | Monitorul de evaluare | Cod sursa (job #423459)
Cod sursa(job #423459)
// Simionescu Andrei, 3/23/2010
// http://infoarena.ro/problema/dfs
// Dificultate: EASY
// Categorii: parcurgere grafuri
#include <cstdio>
using namespace std;
#define NMAX 100005
typedef struct nod
{
int x;
nod *a;
} nod, * pnod;
int n, m, viz[NMAX], cnt;
pnod v[NMAX];
void add( pnod &, int );
void read();
void DFS( int );
int main(){
freopen( "dfs.out", "w", stdout );
read();
for ( int i = 1; i <= n; ++i )
if( !viz[i] )
{
++cnt;
DFS(i);
}
printf( "%d\n", cnt );
return 0;
}
void add( pnod & lst, int val )
{
pnod p;
p = new nod;
p->x = val;
p->a = lst;
lst = p;
}
void read()
{
freopen( "dfs.in", "r", stdin );
scanf( "%d %d", &n, &m );
for( int i = 1, x, y; i <= m; ++i )
{
scanf( "%d %d", &x, &y );
add( v[x], y );
add( v[y], x );
}
}
void DFS(int nod)
{
pnod p;
viz[nod] = 1;
for ( p = v[nod]; p != NULL; p = p -> a)
if( !viz[p -> x] )
DFS(p -> x);
}