Cod sursa(job #2877001)

Utilizator AndreiV03Andrei Voicu AndreiV03 Data 24 martie 2022 00:53:55
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.51 kb
#include <fstream>
#include <queue>
using namespace std;

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

int n, m, k, v[1001][1001], w[1001];

void dfs(int x, int k) {
  w[x] = k;
  
  for (int i = 1; i <= n; ++i)
    if (v[i][x] && !w[i])
      dfs(i, k);
}

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