Cod sursa(job #277641)

Utilizator andrabAndra B andrab Data 11 martie 2009 20:23:21
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream.h>
#define max 100000
#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 citire()
{int i,x,y;
 fin>>n>>m;
 for(i=1;i<=m;i++)
 {fin>>x>>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;
 }