Cod sursa(job #626748)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 28 octombrie 2011 09:29:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <vector>
using namespace std;

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

void dfs(int s){
   int i;
   for(i=0;i<marime[s];i++){
      if(vizitat[lista[s][i]]==0){
           vizitat[lista[s][i]]=1;
           dfs(lista[s][i]);
      }
   }
}

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;
}