Cod sursa(job #2877256)

Utilizator AndreiV03Andrei Voicu AndreiV03 Data 24 martie 2022 14:09:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
#include <vector>
using namespace std;

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

int n, m, k;
bool c[100001];
vector<int> adj[100001];

void dfs(int x) {
  c[x] = 1;

  for (int i = 0; i < adj[x].size(); ++i)
    if (c[adj[x][i]] == 0)
      dfs(adj[x][i]);
}

int main() {
  cin >> n >> m;
  for (int i = 1, a, b; i <= m; ++i) {
    cin >> a >> b;
    adj[a].push_back(b), adj[b].push_back(a);
  }
  
  for (int i = 1; i <= n; ++i)
    if (c[i] == 0)
      dfs(i), ++k;
  
  cout << k;
  
  cin.close();
  cout.close();
  return 0;
}