Cod sursa(job #349426)

Utilizator irene_mFMI Irina Iancu irene_m Data 19 septembrie 2009 15:06:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#define MaxN 100009

struct muchie{
	int x;
	muchie *urm;
};

muchie *G[MaxN];

int n,m,nr,uz[MaxN];

void add(int x,int y)
{
	muchie *aux=new muchie;
	aux->x=y;
	aux->urm=G[x];
	G[x]=aux;
}

void cit()
{
	int i,x,y;
	freopen("dfs.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
}

void DFS(int nod)
{
	muchie *aux=new muchie;
	uz[nod]=1;
	aux=G[nod];
	while(aux)
	{
		if(!uz[aux->x])
			DFS(aux->x);
		aux=aux->urm;
	}
}

void sol()
{
	int i;
	for(i=1;i<=n;i++)
		if(!uz[i])
			DFS(i), nr++;
}

void afis()
{
	freopen("dfs.out","w",stdout);
	printf("%d",nr);
}

int main()
{
	cit();
	sol();
	afis();
	return 0;
}