Cod sursa(job #279916)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 13 martie 2009 08:58:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
//dfs bc

#include <stdio.h>
#define nmax 100002

struct nod {int inf; nod *urm;} *g[nmax];
int n,m,viz[nmax];

void baga(int x, int y)
{
	nod *q=new nod;
	q->inf=y;
	q->urm=g[x];
	g[x]=q;
}

void dfs(int x)
{
	viz[x]=1;
	for(nod *i=g[x];i;i=i->urm)
		if(!viz[i->inf])
			dfs(i->inf);
}

int main()
{
	int i;
	int x,y,nrsol=0;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		baga(x,y);
        baga(y,x);
	}
	for(i=1;i<=n;i++)
		if(!viz[i])
		{
			nrsol++;
			dfs(i);
		}
	printf("%d\n",nrsol);
	fclose(stdout);
	return 0;
}