Cod sursa(job #163176)

Utilizator alex23alexandru andronache alex23 Data 21 martie 2008 16:17:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>

typedef struct nod {
   int val;
   nod *urm;
} *pNod;
pNod a[100001];

int comp_conexe=0,v[100001],n,m;


int citire()
 {FILE *f;
  int x,y;
  pNod q,p;

  f=fopen("dfs.in","r");
  fscanf(f,"%d %d",&n,&m);
  for (int i=1;i<=m;i++)
     {fscanf(f,"%d %d",&x,&y);
      q=new(nod);
      q->val=x;
      q->urm=a[y];
      a[y]=q;
      p=new(nod);
      p->val=y;
      p->urm=a[x];
      a[x]=p;
      }
  fclose(f);
  return 0;

  }

int DFS(int x)
 {
  pNod q;
  for (q=a[x];q!=NULL;q=q->urm)
     if (v[q->val]==0) {v[q->val]=1;
                        DFS(q->val);
                        }
  return 0;
  }

int afisare()
 {FILE *f;

  f=fopen("dfs.out","w");
  fprintf(f,"%d",comp_conexe);
  fclose(f);

  return 0;

  }

int main()
 {
  citire();
  for (int i=1;i<=n;i++)
       if (v[i]==0) {v[i]=1;
                     comp_conexe++;
                     DFS(i);
                     }
  afisare();

  return 0;
  }