Cod sursa(job #527905)

Utilizator avram_florinavram florin constantin avram_florin Data 1 februarie 2011 15:18:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<cstdio>

using namespace std;

int n,m,nr,viz[100005];

typedef struct nod{
			int x;
			nod *urm;
			} *pnod;
pnod a[100005];

void add(pnod &dest,int val)
{
	pnod p;
	p = new nod;
	p -> x = val;
	p -> urm = dest;
	dest = p;
}

void citire()
{
	freopen("dfs.in" , "r" , stdin );
	freopen("dfs.out" , "w" , stdout );
	scanf("%d%d" , &n ,&m );
	int i,x,y;
	for( i = 1 ; i <= m ; i++ )
		{
			scanf("%d%d" , &x , &y);
			add(a[x],y);
			add(a[y],x);
		}
}

void DFS(int nod)
{
	pnod p;
	viz[nod] = 1;
	for( p = a[nod] ; p != NULL ; p = p -> urm )
		if( !viz[p->x] )
			DFS(p->x);
}

int main()
{
	citire();
	int i;
	for( i = 1 ; i <= n ; i++ )
		if( !viz[i] )
			{
				nr++;
				DFS(i);
			}
	printf("%d\n" , nr);
	return 0;
}