Cod sursa(job #696279)

Utilizator gabriel93Robu Gabriel gabriel93 Data 28 februarie 2012 17:49:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<cstring>
using namespace std;
FILE *f,*g;
int n,m,nr,viz[100005];

struct nod
{
	int v;
	nod *adresa;
};
nod *a[100005];

void adaug(int x, int y)
{
	nod *p;
	p=new nod;
	p->v=y;
	p->adresa=a[x];
	a[x]=p;
}

void citire()
{
	int i,x,y;
	f=fopen("dfs.in","rt");
	fscanf(f,"%d %d",&n,&m);
	memset(a,0,sizeof(a));
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d",&x,&y);
		adaug(x,y);
		adaug(y,x);
	}
	fclose(f);
}

void dfs(int x)
{
	nod *p;
	viz[x]=1;
	for(p=a[x];p;p=p->adresa)
		if(viz[p->v]==0)
			dfs(p->v);
}

void scrie()
{
	g=fopen("dfs.out","wt");
	fprintf(g,"%d",nr);
	fclose(g);
}

int main()
{
	int i;
	citire();
	for(i=1;i<=n;i++)
		if(viz[i]==0)
		{
			nr++;
			dfs(i);
		}
	scrie();
	return 0;
}