Cod sursa(job #160159)

Utilizator marinaMarina Horlescu marina Data 14 martie 2008 19:54:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
//dfs - componente conexe
#include <stdio.h>
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
#define NMAX 100001
#define MMAX 200001

int N, M;
int viz[NMAX], ncomp;

struct nod
{
	nod*leg;
	int vec;
}*graf[NMAX];

void DF(int src)
{
	viz[src] = 1;
	nod *p;
	for(p = graf[src]; p; p = p->leg)
		if(!viz[p->vec]) DF(p->vec);
}
int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%d %d", &N, &M);
	
	int i;
	for(i = 1; i <= N; ++i) graf[i] = NULL;
	for(i = 1; i <= M; ++i)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		nod *p = new nod;
		p -> vec = y;
		p -> leg = graf[x];
		graf[x] = p;
		p = new nod;
		p -> vec = x;
		p -> leg = graf[y];
		graf[y] = p;
	}
	
	for(i = 1; i <= N; ++i)
		if(!viz[i])
		{
			++ncomp;
			DF(i);
		}
		
	printf("%d\n", ncomp);
	
	return 0;
}