Cod sursa(job #2196981)

Utilizator georgeromanGeorge Roman georgeroman Data 20 aprilie 2018 20:17:31
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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);

  unsigned numVisited = 0;
  std::stack<unsigned> s;

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

    s.push(first);
    visited[first - 1] = true;
    numVisited++;
    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;
          numVisited++;
          break;
        }
      }
      if (!hasNeighbors) s.pop();
    }

    numComponents++;
  }

  out << numComponents;
  return 0;
}