Cod sursa(job #3164089)

Utilizator MateicostiGoidan Matei-Constantin Mateicosti Data 2 noiembrie 2023 01:49:37
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <vector>
#include <list>
#include <fstream>

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

const int NMAX = 1000000;
std::vector<std::list<int>> L;
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 - 1].push_front(y);
  }
}

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

  std::list<int>::iterator j = L[x].begin();
  while (j != L[x].end()) {
    if (!vis[*j - 1]) {
      dfs(*j - 1);
    }
    j++;
  }
}

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

  L.resize(n);
  making_lists(m);

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

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

  return 0;
}