Cod sursa(job #423459)

Utilizator mordredSimionescu Andrei mordred Data 23 martie 2010 21:34:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
// 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);
}