Cod sursa(job #2001953)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 18 iulie 2017 10:58:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#define NMAX 100001

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

struct nod{
  int val;
  nod * urm;
}* v[NMAX];

int n, m;//date intrare
int componenta[NMAX];
int nrComp;

void initalizare(){
  for(int i = 1; i <= n; i++){
    v[i] = NULL;
    componenta[i] = 0;
  }
}

void citire(){
  in >> n >> m;
  initalizare();
  for(int i = 1; i <= m; i++){
    int x, y;
    in >> x >> y;
    nod * deAd1 = new nod;
    deAd1 -> val = y;
    deAd1 -> urm = v[x];
    v[x] = deAd1;
    nod * deAd2 = new nod;
    deAd2 -> val = x;
    deAd2 -> urm = v[y];
    v[y] = deAd2;
  }
}

void DFS(int plec, int index){
  int stiva[NMAX], vf;
  stiva[1] = plec;
  vf = 1;
  componenta[plec] = index;
  while(vf != 0){
    nod * parcurg = new nod;
    parcurg = v[stiva[vf]];
    bool ok = false;//ver daca vf are vecini nevizitati
    while (parcurg != NULL) {
      if(componenta[parcurg -> val] == 0){
        ok = true;
        componenta[parcurg -> val] = index;
        stiva[++vf] = parcurg -> val;
        parcurg = NULL;
      }
      else parcurg = parcurg -> urm;
    }
    if(ok == false)
      vf --;
  }
}

void rezolvare(){
  for(int i = 1; i <= n; i++)
    if(componenta[i] == 0){
      nrComp++;
      DFS(i, nrComp);

    }
}
void afisare(){
  out << nrComp;
}

int main(){
  citire();
  rezolvare();
  afisare();
  return 0;
}