Cod sursa(job #149099)

Utilizator mariaciPopa Marius Ionut mariaci Data 5 martie 2008 12:32:26
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<stdio.h>
int viz[1000],n,nc,m;
typedef struct nod
{ int x;
  nod *next;
}*pNod;
pNod v[1000];
void add(int x,int y)
{ pNod p;
  p=new nod;
  p->x=x;
  p->next=v[y];
  v[y]=p;
}
void citire()
{ freopen("dfs.in","r",stdin);
  freopen("dfs.out","w",stdout);
  scanf("%d%d",&n,&m);
  int i,x,y;
  for(i=1;i<=m;i++)
     { scanf("%d%d",&x,&y);
       add(x,y);add(y,x);
     }
}
void df(int nod)
{ pNod p;
  viz[nod]=1;
  for(p=v[nod];p!=NULL;p=p->next)
      if(!viz[p->x])
	   df(p->x);
}
int main()
{ citire();
  int i;
  for(i=1;i<=n;i++)
     if(!viz[i])
       { nc++;
	 df(i);
       }
  printf("%d\n",nc);
  return 0;
}