Cod sursa(job #695140)

Utilizator razvan2006razvan brezulianu razvan2006 Data 28 februarie 2012 10:44:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<algorithm>
#include<stdio.h>
#define NMAX 100001
using namespace std;
long i, j, n, m, viz[NMAX];

typedef struct nod
{
	int x; 
	nod *a;
} *pNod;
pNod v[NMAX];

void dfs(int node)
{
	pNod p;
	viz[node] = 1;
	for(p = v[node]; p != NULL; p = p->a)
		if(viz[p->x] == 0) dfs(p->x);
}

int main()
{
	freopen("dfs.in", "rt", stdin);
	freopen("dfs.out", "wt", stdout);
	
	scanf("%ld%ld", &n, &m);
	pNod p;
	long x, y;
	
	for(int i = 1; i <= m; i++)	{
		scanf("%ld %ld", &x, &y);
		p = new nod;
		p->x = x; p->a = v[y]; v[y] = p;
		p = new nod;
		p->x = y; p->a = v[x]; v[x] = p;
	}
	
	long cnt = 0;
	for(int i = 1; i <= n; i++)
		if(viz[i] == 0)	{
			cnt++; dfs(i);
		}
	
	printf("%ld\n", cnt);

	return 0;
}