Cod sursa(job #325584)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 21 iunie 2009 13:44:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <cstdlib>

#define Nmax 100100
#define file_in "dfs.in"
#define file_out "dfs.out"

struct Nod
{
	int inf;
	struct Nod *urm;} *Lista[Nmax];

int n,m;
int viz[Nmax];


void add(int x, int y)
{
	Nod *q=new Nod;
	q->inf=y;
	q->urm=Lista[x];
	Lista[x]=q;
}

void dfs(int nod)
{
	Nod *p;  
	viz[nod]=1;
	for (p=Lista[nod];p;p=p->urm)
		 if (!viz[p->inf])
			  dfs(p->inf);
}

int main()
{
	int i,x,y;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	scanf("%d %d", &n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &x,&y);
		add(x,y);
		add(y,x);
	}
	
	int nr=0;
	
	for (i=1;i<=n;++i)
	    if (!viz[i])
		{
		dfs(i);
		nr++;
	    }
	
	printf("%d", nr);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}