Cod sursa(job #2610436)

Utilizator cristi1616Olaru Cristian cristi1616 Data 4 mai 2020 21:13:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100009

class Task {
public:
  void solve() {
    read_input();
    get_result();
    print_output();
  }

private:
  int n, m, cc;
  vector<int> adj[NMAX];

  void read_input() {
  	ifstream fin("dfs.in");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
      int x, y;
      fin >> x >> y;

      adj[x].push_back(y);
      adj[y].push_back(x);
    }
    fin.close();
  }

  void get_result() {
    do_dfs();
  }

  void do_dfs() {
  	cc = 0;
    vector<int> used(n + 1);
    for (int i = 1; i <= n; ++i) {
      used[i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
      if (!used[i]) {
      	++cc;
        dfs(i, used);
    	}
  	}
  }

  void dfs(int node, vector<int> &used) {
    used[node] = 1;
    for (auto &it : adj[node]) {
      if (!used[it]) {
        dfs(it, used);
      }
    }
  }

  void print_output() {
  	ofstream fout("dfs.out");
  	fout << cc << "\n";
  	fout.close();
  }
};

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