Cod sursa(job #288013)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 25 martie 2009 14:21:41
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<iostream>
#include<stdio.h>
struct nod {int inf;nod *next;};
nod *v[100010];
bool ut[100010];
void add(nod *&v,int y)
{
   nod *c=new nod;
   c->next=v;
   c->inf=y;
   v=c;
}
void dfs(int nd)
{
   ut[nd]=1;
   while(v[nd])
   {
      if(!ut[v[nd]->inf])
	 dfs(v[nd]->inf);
      v[nd]=v[nd]->next;
   }
}
int main()
{
   freopen("dfs.in","r",stdin);
   freopen("dfs.out","w",stdout);
   int n,m,i,nr;
   scanf("%d%d",&m,&n);
   for(i=1;i<=n;i++)
   {
      int x,y;
      scanf("%d%d",&x,&y);
      add(v[x],y);
      add(v[y],x);
   }
   for(i=1;i<=n;i++)
      if(!ut[i])
      {
	 nr++;
	 dfs(i);
      }
   printf("%d\n",nr);
}