Cod sursa(job #2780433)

Utilizator mvoineaVoinea Mihai-Alexandru mvoinea Data 6 octombrie 2021 23:20:14
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

class Graph
{
private:
  int nodes_count;
  int edges_count;

  unordered_map<int, vector<int>> edges;

  void addEdge(int a, int b)
  {
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  queue<int> _dfs(int node, vector<bool> &visited)
  {
    queue<int> result;
    stack<int> stack;

    stack.push(node);

    while (!stack.empty())
    {
      int topNode = stack.top();
      stack.pop();

      if (!visited[topNode])
      {
        result.push(topNode);
        visited[topNode] = true;
      }

      for (int adjacentEdge : edges[topNode])
      {
        if (!visited[adjacentEdge])
          stack.push(adjacentEdge);
      }
    }

    return result;
  }

public:
  int connectedComponents()
  {
    int connectedComponentsCount = 0;
    vector<bool> visited(nodes_count + 1, false);
    for (int node = 1; node < nodes_count + 1; node++)
      if (!visited[node])
      {
        _dfs(node, visited);
        connectedComponentsCount++;
      }

    return connectedComponentsCount;
  }
  queue<int> dfs(int node)
  {
    vector<bool> visited(nodes_count + 1, false);
    return _dfs(node, visited);
  }

  void readFromFile(string filePath)
  {
    ifstream input = ifstream(filePath);
    input >> nodes_count;
    input >> edges_count;

    for (int i = 0; i < edges_count; i++)
    {
      int a, b;
      input >> a >> b;
      addEdge(a, b);
    }
  }
};

int main()
{
  ofstream output("dfs.out");
  Graph g = Graph();

  g.readFromFile("dfs.in");
  output << g.connectedComponents();
  return 0;
}