Cod sursa(job #662967)

Utilizator attila3453Geiszt Attila attila3453 Data 17 ianuarie 2012 16:22:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>
#include <stdio.h>

using namespace std;

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

vector<int> *vecini;
bool* vizitate;
int nnv, ncc;

void dfs(int start)
{
  vizitate[start] = 1;
  nnv++;
  unsigned int i;
  for(i = 0;i<vecini[start].size();i++)
    if(!vizitate[vecini[start][i]])
      dfs(vecini[start][i]);
}

int main () {
  int i, nrnoduri, nrmuchii, a, b;

  fi>>nrnoduri>>nrmuchii;

  vecini = new vector<int>[nrnoduri+1];
  vizitate = new bool[nrnoduri+1];

  for(i = 0;i < nrmuchii;i++)
  {
    fi>>a>>b;
    vecini[a].push_back(b);
    vecini[b].push_back(a);
  }

  for (i = 1; i <= nrnoduri; i++)
    if (!vizitate[i])
    {
      ncc++;
      dfs(i);
    }

  fo << ncc;
  return 0;
}