Cod sursa(job #2143039)

Utilizator futurengineerOana Rosca futurengineer Data 25 februarie 2018 15:17:23
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>

using namespace std;

int noduri, muchii, comp_conexe, x, y;
bool marcat[100001];
vector<int>vec[100001];

void dfs(int nod) {
  vector<int>::iterator i;

  marcat[nod] = true;
  for (i = vec[nod].begin(); i != vec[nod].end(); i++)
    if (!marcat[*i])
      dfs(*i);
}

int main () {
  ifstream fi("dfs.in");
  ofstream fo("dfs.out");
  fi >> noduri >> muchii;
  for (int i = 1; i <= noduri; i++)
    fi >> x >> y, vec[x].push_back(y);
  for (int i = 1; i <= noduri; i++)
    if (!marcat[i])
      comp_conexe++, dfs(i);
  fo << comp_conexe;
  return 0;
}