Cod sursa(job #269348)

Utilizator razyelxrazyelx razyelx Data 2 martie 2009 20:10:14
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream.h>
#define MAX 100001
ifstream in("dfs.in");
ofstream out("dfs.out");
struct NOD{ int info;
	    NOD *urm;} *VF[MAX];

int k,n,m,s[MAX],d[MAX],st[MAX],prim,ultim;

void init(){
     int i;
     for(i=1;i<=n;++i)s[i]=0;
}

void adauga(NOD *&prim,int y){
     NOD *p;
     p = new NOD;
     p->info = y;
     p->urm = prim;
     prim = p;
}
void citire(){
     int x,y;
     in>>n>>m;

     while(in>>x>>y)
	  adauga(VF[x],y);
}
void parcurge(int i){
    int j=0;
    NOD *q;

    prim = ultim = 1;
    s[i] = 1;
    st[prim] = i;

    while(prim<=ultim && j<n){

	 for(q = VF[st[prim]];q!=NULL;q=q->urm)
	    if(!s[q->info])
	    {
	      st[++ultim] = q->info;
	      s[q->info] = k;

	      j++;
	    }

	 prim++;
    }
}
int main(){
    citire();

    for(int i=1;i<=n;++i)
       if(!s[i]){
	 k++;
	 parcurge(i);
       }
    out<<k;
    return 0;
}