Cod sursa(job #2210528)

Utilizator CiobaCatalinCioba Catalin CiobaCatalin Data 6 iunie 2018 21:43:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int m, n, s;
vector<int> *adj;
vector<bool> visited;

void dfs(int s) {

  for (auto el : adj[s]) {
    if (!visited[el]) {
      visited[el] = true;
      dfs(el);
    }
  }
}

int main() {
  ifstream in;
  ofstream out;

  in.open("dfs.in");
  out.open("dfs.out");

  in >> n >> m;
  adj = new vector<int>[n + 1];
  visited.resize(n + 1, false);

  int x, y;
  for (int i = 0; i < m; ++i) {
    in >> x >> y;

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

  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    if (!visited[i]) {
      ++cnt;
      dfs(i);
    }
  }

  out << cnt;

  in.close();
  out.close();

  return 0;
}