Cod sursa(job #2424472)

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

using namespace std;

class graph {
  int vertices;
  int edges;
  vector<vector<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++) {
      vector<int>* insertMe = new vector<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);
      g.adjacency[r2].push_back(r1);
    }
    return in;
  }

public:
  void dfs(int orig) {
    visited[orig] = true;
    for (auto neighbour : adjacency[orig]) {
      if (!visited[neighbour])
        dfs(neighbour);
    }
  }

  int components() {
    int count = 0;
    for (int i = 1; i <= vertices; i++) {
      if (!visited[i]) {
        dfs(i);
        visited[i] = true;
        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;
}