Cod sursa(job #269415)

Utilizator razyelxrazyelx razyelx Data 2 martie 2009 21:23:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 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],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);
	  adauga(VF[y],x);
     }
}

void parcurge(int i){
    NOD *q;
    s[i] = k;

    for(q=VF[i];q!=NULL;q=q->urm) if(!s[q->info])parcurge(q->info);
}
int main(){
    citire();

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