Cod sursa(job #2610263)

Utilizator RobertLicaRobert Lica RobertLica Data 4 mai 2020 17:50:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

#define FILE_I "dfs.in"
#define FILE_O "dfs.out"

class Task {
  int n, m;
  int no_cox = 0;
  std::vector< std::vector< int>> adj;

 public:
  void solve() {
    read();
    fa();
    print();
  }

 private:
  void read() {
    std::ifstream fin(FILE_I);
    fin >> n >> m;
    adj.resize(n + 1);

    int x, y;
    for (int i = 0; i < m; ++i) {
      fin >> x >> y;
      adj[x].push_back(y);
      adj[y].push_back(x);
    }
    fin.close();
  }

  void fa() {
    std::vector<int> vizitat(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
      if (vizitat[i] == 0) {
        ++no_cox; 
        dfs(i, vizitat);
        // std::cout << std::endl;
      }
    }
  }

  void dfs(int nod, std::vector<int> &vizitat) {
    // std::cout << nod << " ";
    vizitat[nod] = 1;
    for (auto &x : adj[nod]) {
      if (vizitat[x] == 0) {
        dfs(x, vizitat);
      }
    }
  }

  void print() {
    std::ofstream fout (FILE_O);
    fout << no_cox;
    fout.close();
  }
};

int main() {
  Task *t = new Task();
  t->solve();
  delete t;
  return 0;
}