Cod sursa(job #147164)

Utilizator FlorianFlorian Marcu Florian Data 2 martie 2008 17:21:38
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");
typedef struct NOD
  {
  int info;
  NOD *urm;
  }Nod;
Nod *prim[100003];
void insert(int x, int y)
 {
 Nod *p;

 p=new Nod;
 p->info=y;
 p->urm=prim[x];
 prim[x]=p;

 p=new Nod;
 p->info=y;
 p->urm=prim[y];
 prim[y]=p;
 }
int viz[100002],k,n;
void read()
 {
 int m,x,y;
 fscanf(f,"%d %d",&n,&m);
 while(m--)
  {
  fscanf(f,"%d %d",&x,&y);
  insert(x,y);
  }
 }
void DF(int x)
  {
  Nod *q;
  viz[x]=k;
  for(q=prim[x];q;q=q->urm)
   if(viz[q->info]==0) DF(q->info);
  }
void solve()
 {
 int i;
 for(i=1;i<=n;++i)
  if(viz[i]==0)
   {
   k++;
   DF(i);
   }
 fprintf(g,"%d\n",k);
 }
int main()
 {
 read();
 solve();
 return 0;
 }