Cod sursa(job #2975637)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 6 februarie 2023 22:26:31
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <memory>
#include <vector>

using namespace std;

class Solver{
private: 
  void DFS(int k, const vector<vector<int>>& Graph, vector<bool> *used) {
    (*used)[k] = true;
    for (auto v: Graph[k])
      if(!(*used)[v])
	DFS(v, Graph, used);
  }
  
  int countCC(const vector<vector<int>>& Graph) {
    int connectedComp = 0;
    vector<bool> used((int)Graph.size());
    for (int i = 0; i < (int)Graph.size(); ++i)
      if (!used[i]) {
	DFS(i, Graph, &used);
	++connectedComp;
      }
    return connectedComp;
  }
  
public:
  Solver() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
  }
  ~Solver() {
    fclose(stdin);
    fclose(stdout);
  }

  void execute() {
    int N, M;
    scanf("%d%d", &N, &M);
    vector<vector<int>> Graph(N);
    int from, to;
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &from, &to);
      Graph[from].emplace_back(to);
      Graph[to].emplace_back(from);
    }
    printf("%d", countCC(Graph));
  }
};

int main() {
  unique_ptr<Solver> s = make_unique<Solver>();
  s->execute();
  return 0;
}