Cod sursa(job #2196979)

Utilizator georgeromanGeorge Roman georgeroman Data 20 aprilie 2018 20:05:30
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <stack>
#include <vector>
#include <iostream>

int main() {
  std::ifstream in("dfs.in");
  std::ofstream out("dfs.out");

  unsigned n, m;
  in >> n >> m;

  std::vector<std::vector<unsigned>> graph = std::vector<std::vector<unsigned>>();
  graph.reserve(n);
  for (unsigned i = 0; i < n; i++) graph.push_back(std::vector<unsigned>());

  for (unsigned i = 0; i < m; i++) {
    unsigned v1, v2;
    in >> v1 >> v2;
    graph[v1 - 1].push_back(v2);
    graph[v2 - 1].push_back(v1);
  }

  unsigned numComponents = 0;

  std::vector<bool> visited = std::vector<bool>();
  visited.reserve(n);
  for (unsigned i = 0; i < n; i++) visited.push_back(false);

  bool done = false;
  while (!done) {
    unsigned first = 1;
    for (unsigned i = 0; i < n; i++) {
      if (!visited[i]) {
        first = i + 1;
        break;
      }
    }

    std::stack<unsigned> s = std::stack<unsigned>();
    s.push(first);
    visited[first - 1] = true;
    while (!s.empty()) {
      unsigned current = s.top();
      bool hasNeighbors = false;
      for (unsigned v : graph[current - 1]) {
        if (!visited[v - 1]) {
          hasNeighbors = true;
          s.push(v);
          visited[v - 1] = true;
          break;
        }
      }
      if (!hasNeighbors) s.pop();
    }

    numComponents++;

    done = true;
    for (bool b : visited) {
      if (b == false) done = false;
    }
  }

  out << numComponents;
  return 0;
}