Cod sursa(job #3164093)

Utilizator MateicostiGoidan Matei-Constantin Mateicosti Data 2 noiembrie 2023 02:00:10
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <vector>
#include <fstream>

std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");

const int NMAX = 1000000;
std::vector<int> L[NMAX + 1];
int vis[NMAX];

void making_lists(int m) {
  // Making the ajacengy list 
  for (int i = 0; i < m; i++) {
    int x, y;
    fin >> x >> y;

    L[x].push_back(y);
    L[y].push_back(x);
  }
}

void dfs(int x) {
  //std::cout << x << " ";
  vis[x] = 1;

  for(auto var : L[x]) {
    if (!vis[var]) {
      dfs(var);
    }
  }
}

int main (int argc, char *argv[]) {
  // Test if the file has succesfully open
  if (!fin.is_open()) {
    std::cout << "Error: Failed to open file." << std::endl;    
    exit(1);
  }

  int n, m, numb = 0;

  // Reading graph data
  fin >> n;                 // Number of nodes
  fin >> m;                 // Number of vertices

  making_lists(m);

  for (int i = 1; i < n; i++) {
    if (vis[i] == 0) {
      numb++;
      dfs(i);
    }
  }

  fout << numb;
  
  fin.close();
  fout.close();

  return 0;
}