Cod sursa(job #1527310)

Utilizator paul-gPaul Grigoras paul-g Data 17 noiembrie 2015 23:17:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stack>
#include <vector>
#include <fstream>
#include <iostream>

using namespace std;

int main() {
  ifstream f{"dfs.in"};
  ofstream g{"dfs.out"};

  int n, m;
  f >> n >> m;

  vector<vector<int>> edges(n);
  for (int i = 0; i < m; i++) {
    int s, d;
    f >> s >> d;
    s--; d--;
    edges[s].push_back(d);
    edges[d].push_back(s);
  }

  vector<int> seen(n, 0);
  int i = 0;
  int seen_nodes = 0;
  int comps = 0;
  while (seen_nodes < n) {
    //std::cout << " i = " << i << std::endl;
    while (i < seen.size() && seen[i] == 1)
      i++;
    if (i == seen.size())
      break;

    // i is source
    stack<int> fringe;
    fringe.push(i);
    while (!fringe.empty()) {
      int next = fringe.top();
      //std::cout << " next = " << next << std::endl;
      fringe.pop();

      if (seen[next])
        continue;
      seen[next] = 1;
      seen_nodes++;
      //std::cout << " process = " << next << std::endl;

      for (auto e : edges[next]) {
        if (!seen[e]) {
          fringe.push(e);
        }
      }
    }
    comps++;
  }
  g << comps << endl;
  return 0;
}