Cod sursa(job #499167)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 8 noiembrie 2010 21:59:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<cstdio>
#define NMAX 100001
using namespace std;

struct NodGR
{
	int inf;
	struct NodGR* next;
};

typedef NodGR* NGR;

NGR a[NMAX];
int n,viz[NMAX],i,nr;

void read();
void DFS(int x);
void adaug(int x,int y);

int main()
{
	freopen ("dfs.in","r",stdin);
	freopen ("dfs.out","w",stdout);
	read();
	for (i=1;i<=n;++i)
		if (!viz[i])
		{
			++nr;
			DFS(i);
		}
	printf("%ld",nr);
	return 0;
}

void read()
{
	int m,i,x,y;
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%ld%ld",&x,&y);
		adaug(x,y);
		adaug(y,x);
	}
}

void adaug(int x,int y)
{
	NGR p=new NodGR;
	p->inf=y;
	p->next=a[x];
	a[x]=p;
}

void DFS(int x)
{
	NGR i;
	for (i=a[x];i;i=i->next)
		if (!viz[i->inf])
		{
			viz[i->inf]=1;
			DFS(i->inf);
		}
}