Cod sursa(job #3368082)

Utilizator nstefanNeagu Stefan nstefan Data 13 octombrie 2026 10:53:11
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
// https://infoarena.ro/problema/dfs
#include <bits/stdc++.h>
#include <deque>
using namespace std;

int main() {
  int n; cin >> n;
  int m; cin >> m;
  vector<vector<int>> graph;
  graph.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int a; int b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  int num_comp = 0;
  vector<int> cc;
  cc.resize(n + 1);

  // cout << n << ' ' << m << '\n';
  // for (int i = 1; i <= n; i++) {
  //   cout << i << ": ";
  //   for (auto n : graph[i]) {
  //     cout << n << " ";
  //   }
  //   cout << "\n";
  // }

  for (int source_node = 1; source_node <= n; source_node++) {
    if (cc[source_node] != 0)
      continue;
    num_comp++;

    deque<int> dq;
    dq.push_back(source_node);

    while (!dq.empty()) {
      int node = dq.back(); dq.pop_back();
      if (cc[node] != 0) continue;
      cc[node] = num_comp;

      for (auto neigh : graph[node]) {
        if (cc[neigh] != 0) continue;
        dq.push_front(neigh);
      }
    }
  }

  cout << num_comp;

  return 0;
}