Cod sursa(job #277649)

Utilizator andrabAndra B andrab Data 11 martie 2009 20:29:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream.h>
#define max 100004
#define maxm max*(max-1)/2


ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n,m,v[max],nc;
struct nod {int info;
	     nod *urm;
	     };
nod *l[max];
void adauga(int x,int y);

void citire()
{int i,x,y;
 fin>>n>>m;
 for(i=1;i<=m;i++)
 {fin>>x>>y;
  adauga(x,y);
  adauga(y,x);
  }
 }

  void adauga(int x,int y)
  {nod *d;
   d=new nod;
   d->info=y;
   d->urm=l[x];
   l[x]=d;
  }


void dfs(int i)
{v[i]=1;
 nod *d;
 d=l[i];
 while(d)
 {if(v[d->info]==0) dfs(d->info);
  d=d->urm;
  }

 }


int main()
{int i; nc=0;
 citire();

 for(i=1;i<=n;i++)
 if(v[i]==0) {dfs(i);
	      nc++;
	      }

 fout<<nc;

 fin.close();
 fout.close();

 return 0;
 }