Cod sursa(job #2424465)

Utilizator PasarelAlex Oltean Pasarel Data 23 mai 2019 01:04:57
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;

class graph {
  int vertices;
  int edges;
  vector<list<int>> adjacency;
  vector<bool> visited;
  friend istream& operator>>(istream& in, graph& g) {
    int r1, r2;
    in >> g.vertices >> g.edges;
    for (int i = 0; i <= g.vertices; i++) {
      list<int> *insertMe = new list<int>;
      g.adjacency.push_back(*insertMe);
      g.visited.push_back(false);
    }
    for (int i = 0; i < g.edges; i++) {
      in >> r1 >> r2;
      g.adjacency[r1].push_back(r2);
    }
    return in;
  }

public:
  void dfs(int orig) {
    int popped;
    vector<int> stack;
    stack.push_back(orig);
    while (!stack.empty()) {
      popped = stack.front();
      stack.erase(stack.begin());
      if (!visited[popped]) {
        visited[popped] = true;
        for (auto neighbour : adjacency[popped]) {
          stack.push_back(neighbour);
        }
      }
    }
  }

  int components() {
    int count = 0;
    for (int i = 0; i < vertices; i++) {
      if (!visited[i]) {
        dfs(i);
        count++;
      }
    }
    return count;
  }
};

int main() {
  graph G;
  ifstream in("dfs.in");
  in >> G;
  in.close();
  ofstream out("dfs.out");
  out << G.components();
  out.close();
  return 0;
}