Cod sursa(job #189639)

Utilizator katakunaCazacu Alexandru katakuna Data 16 mai 2008 15:02:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>

struct nod {int v; nod *a;};
nod *a[100010];
int nr,viz[100010],n,m,i,x,y;
nod *p;


void DFS (int x){
int i;

viz[x]=1;
p=a[x];

  for(nod *p = a[x];p!=NULL;p=p->a){
    if(!viz[p->v])
    DFS(p->v);
  }

}



int main(){


FILE *f=fopen("dfs.in","r");
fscanf(f,"%d %d",&n,&m);

  for(i=1;i<=n;i++)
  a[i]=NULL;

  for(i=1;i<=m;i++){
  fscanf(f,"%d %d",&x,&y);
 nod *p=new nod;
  p->v=y;
  p->a=a[x];
  a[x]=p;

 nod *q=new nod;
  q->v=x;
  q->a=a[y];
  a[y]=q;
  }


fclose(f);


  for(i=1;i<=n;i++){
    if(!viz[i]){
    nr++;
    DFS(i);
    }
  }
  


FILE *g=fopen("dfs.out","w");
fprintf(g,"%d",nr);
fclose(g);


return 0;
}