Cod sursa(job #607929)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 13 august 2011 20:00:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <stdio.h>
#define max 100001
using namespace std;
struct art{int val; art *urm; }*q;
art *p[max],*aux;
int main()
{
FILE *f,*g;
int nc,a,b,m,n,viz[max],i,c[max],u,pr;
f=fopen("dfs.in","r");
g=fopen("dfs.out","w");
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=m;i++)
{fscanf(f,"%d %d",&a,&b);
 aux=new art;
 aux->val=b;
  aux->urm=p[a];
	p[a]=aux;
	aux=new art;
	aux->val=a;
	aux->urm=p[b];
	p[b]=aux;
}
for(i=1;i<=n;i++)viz[i]=0;

nc=0;
for(i=1;i<=n;i++)
{
	if(viz[i]==0){    pr=1;u=1;viz[i]=1;
					  c[1]=i;
						while(pr<=u)
						{aux=p[c[pr]];
						while(aux!=NULL)
							{
								
							if(viz[aux->val]==0){viz[aux->val]=1;u++;c[u]=aux->val;}
							aux=aux->urm;
							}
						pr++;
						}
					  nc++;
	              }
}
fprintf(g,"%d",nc);
fclose(f);
fclose(g);
return 0;
}