Cod sursa(job #1761427)

Utilizator oanaroscaOana Rosca oanarosca Data 22 septembrie 2016 10:41:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <fstream>
#include <vector>

using namespace std;

bool viz[100001];
int n, m, i, x, y, cc;
vector<int> vec[100001];

void dfs (int nod) {
  vector<int>::iterator i;
  viz[nod] = true;
  for (i = vec[nod].begin(); i < vec[nod].end(); i++)
    if (not viz[*i])
      dfs(*i);
}

int main () {
  ifstream fi("dfs.in");
  ofstream fo("dfs.out");
  fi >> n >> m;
  for (i = 1; i <= m; i++)
    fi >> x >> y, vec[x].push_back(y), vec[y].push_back(x);
  for (i = 1; i <= n; i++)
    if (not viz[i])
      cc++, dfs(i);
  fo << cc;
  return 0;
}