Cod sursa(job #1952846)

Utilizator Ionut228Ionut Calofir Ionut228 Data 4 aprilie 2017 13:48:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int NMAX = 100001;

int n, m;
int sol;
vector<int> v[NMAX];
bool used[NMAX];

void dfs(int nod) {
  for (vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) {
    if (!used[*it]) {
      used[*it] = true;
      dfs(*it);
    }
  }
}

int main() {
  fin >> n >> m;

  for (int i = 1, nod1, nod2; i <= m; ++i) {
    fin >> nod1 >> nod2;
    v[nod1].push_back(nod2);
    v[nod2].push_back(nod1);
  }

  sol = 0;
  for (int i = 1; i <= n; ++i) {
    if (!used[i]) {
      used[i] = true;
      ++sol;
      dfs(i);
    }
  }

  fout << sol << '\n';
  return 0;
}