Cod sursa(job #632724)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 12 noiembrie 2011 10:29:33
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
//variante 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=0;//incep sa caut vecini de aici
   while(vf>=0){
    s=stiva[vf].nod;
    while(stiva[vf].vecin<marime[s]){
       if(vizitat[lista[s][stiva[vf].vecin]]==0){
           vizitat[lista[s][stiva[vf].vecin]]=1;
           vf++;
           //dfs(lista[s][i]);
           stiva[vf].nod=lista[s][stiva[vf].vecin];
           stiva[vf].vecin=0;
      }
      stiva[vf].vecin++;
     }
     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 pronind de la nodul i
        dfs(i);
        conex++;
     }
  }
  FILE *fout=fopen("dfs.out","w");
  fprintf(fout,"%d\n",conex);
  fclose(fout);
return 0;
}