Cod sursa(job #2519451)

Utilizator CristiVintilacristian vintila CristiVintila Data 7 ianuarie 2020 19:20:31
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int nrcomp, frecv[250000];
int vertices, edges;
vector<int> gr[250000];

void DFS(int nod) {
  frecv[nod] = nrcomp;
  for (int i = 0; i < gr[nod].size(); i++)
    if (!frecv[i])
      DFS(i);
}

void comp() {
  for (int i = 0; i < edges; i++)
    if (frecv[i] == 0) {
      nrcomp++;
      DFS(i);
    }
}

int main(int argc, const char * argv[]) {
  fin >> vertices >> edges;
  for (int i = 0; i < edges; i++) {
    int x, y;
    fin >> x >> y;
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
  comp();
  fout << nrcomp;
}