Cod sursa(job #632760)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 12 noiembrie 2011 11:50:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
//varianta iterativa

#include <stdio.h>
#include <vector>
#define NMAX 100010
using namespace std;



vector <int> lista[NMAX];
char vizitat[NMAX];
int marime[NMAX];

struct nod{
   int vecin, nod;
}stiva[NMAX];


void dfs(int s){
   int i;
   int vf=0;
   vizitat[s]=1;
   stiva[vf].nod=s;
   stiva[vf].vecin=-1;//incep sa caut vecini de aici
   while(vf>=0){
    //pun un vecin al varfului stivei in stiva
    while((++(stiva[vf].vecin))<marime[stiva[vf].nod]){
       if(vizitat[lista[stiva[vf].nod][stiva[vf].vecin]]==0){
           vizitat[lista[stiva[vf].nod][stiva[vf].vecin]]=1;
           vf++;
           stiva[vf].nod=lista[stiva[vf-1].nod][stiva[vf-1].vecin];
           stiva[vf].vecin=-1;
      }
     }
     vf--;
   }
}

int main(){
  int n,m;
  int i;
  int a,b;
  int conex=0;
  FILE *fin=fopen("dfs.in","r");
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<m;i++){
     fscanf(fin,"%d%d",&a,&b);
     a--;b--;
     lista[a].push_back(b);
     marime[a]++;
     lista[b].push_back(a);
     marime[b]++;
  }
  fclose(fin); 
  //lista[i] contine toti vecinii nodului i
  for(i=0;i<n;i++){
     if(vizitat[i]==0){
        //fac o parcurgere pornind de la nodul i
        dfs(i);
        conex++;
     }
  }
  FILE *fout=fopen("dfs.out","w");
  fprintf(fout,"%d\n",conex);
  fclose(fout);
return 0;
}