Cod sursa(job #3250544)

Utilizator stefan0211Tacu Darius Stefan stefan0211 Data 21 octombrie 2024 20:02:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");
int m, n, s;
vector<vector<int>> lista;
vector<int> viz;

void DFS(int x) {
  // Setăm x ca fiind vizitat (dar gri)
  viz[x] = 1;

  // luam ca fiind y un vecin al lui x
  for (auto &y : lista[x]) {
    if (viz[y] == 0) {
      // reapelăm pentru fiecare vecin
      DFS(y);
    }
  }
}

int main() {
  f >> n >> m;
  int x1, x2;
  lista.resize(n + 1);
  viz.resize(n + 1);

  for (int i = 1; i <= m; i++) {
    f >> x1 >> x2;
    lista[x1].push_back(x2);
    lista[x2].push_back(x1);
  }

  int nr_componente = 0;
  for (int i = 1; i <= n; i++) {
    if (viz[i] == 0) {
      DFS(i);
      nr_componente++;
    }
  }

  g << nr_componente;

  f.close();
  g.close();

  return 0;
}