Cod sursa(job #2793763)

Utilizator YusyBossFares Yusuf YusyBoss Data 3 noiembrie 2021 23:23:07
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <vector>
#define NMAX 100000

using namespace std;

ifstream cin ("dfs.in");
ofstream cout ("dfs.out");

bool mark[NMAX + 1];
vector <int> vnext[NMAX + 1];

void dfs(int node) {
  int n, i;

  mark[node] = 1;
  n = vnext[node].size();
  for (i = 0; i < n; i++)
    if (!mark[vnext[node][i]])
      dfs(vnext[node][i]);
}

int main() {
  int n, m, i, a, b, sol;
  cin >> n >> m;

  for (i = 0; i < m; i++) {
    cin >> a >> b;
    vnext[a].push_back(b);
  }

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

  cout << sol;
  return 0;
}