Cod sursa(job #412791)

Utilizator cosgbCosmin cosgb Data 5 martie 2010 23:46:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
# include <stdio.h>
long n,m;
long viz[100005],q[100005];

struct nod
{ nod * urm;
  long info;};
nod * v[100005];

void read()
{ nod *p;
long i,a,b;
  for (i=1;i<=m;i++)
    {scanf ("%ld%ld",&a,&b);
     p=new nod;
     p->info=b;
     p->urm=v[a];
     v[a]=p;
     p=new nod;
     p->info=a;
     p->urm=v[b];
     v[b]=p;
    }
}

void dfs(long i)
{ viz[i]=1; 
if (v[i]==NULL)
	   return;
  nod *p;
  p=v[i];
  while (p)
  { if (viz[p->info]==0)
         {viz[p->info]=1;
          dfs(p->info);
		 }
		 p=p->urm;
  }		 
}


void rezolvare()
{long i,nr=0;
 for (i=1;i<=n;i++)
	 if (viz[i]==0)
	     {nr++;
	      dfs(i);
		 }
		printf ("%ld",nr);
}
	      
 
  
  
  
  int main()
{ freopen ("dfs.in","r",stdin);
  freopen ("dfs.out","w",stdout);
  scanf ("%ld%ld%", &n,&m);
  read();
  rezolvare();
  return 0;
}