Cod sursa(job #854263)

Utilizator ioanapopaPopa Ioana ioanapopa Data 13 ianuarie 2013 01:11:06
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#include<algorithm>

using namespace std;

#define nMax 100001

int N, M, use[nMax], T[nMax];

struct lista {
	int nod;
	lista *urm;
	} *G[nMax];

void add(int x, int y )
{
	lista *p;
	//p = new lista;

	p->nod = y;
	p->urm = G[x];
	G[x] = p;
}

void Read()
{
	freopen ( "dfs.in", "r", stdin );
	scanf ( "%d %d", &N, &M );
	
	int i, j;

	for(; M; M--)
	{
		scanf ( "%d %d", &i, &j );
		add(i, j);
		add(j, i);
	}
	
	fclose(stdin);
}

void DF(int sursa)
{
	lista *p;
	
	use[sursa] = 1;
	
	for(p=G[sursa]; p!=NULL; p=p->urm)
		if( !use[p->nod] )
		{
			T[p->nod] = sursa;
			DF(p->nod);
		}
}

int main()
{
	Read();
	int Nr=0;

	for(int i=1; i<=N; i++)
		if( !use[i] )		
		{
			DF(i);
			Nr++;
		}

	freopen ( "dfs.out", "w", stdout );
	
	printf ( "%d\n", Nr );

	fclose(stdout);
	
	return 0;
}