Cod sursa(job #2798836)

Utilizator vladburacBurac Vlad vladburac Data 11 noiembrie 2021 23:22:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;

ifstream fin( "dfs.in" );
ofstream fout( "dfs.out" );

vector <int> edges[NMAX+1];
int stare[NMAX+1];

void dfs( int a ) {
  stare[a] = 1;
  for( auto i : edges[a] ) {
    if( stare[i] == 0 )
      dfs( i );
  }
}

int main() {
  int n, m, a, b, nr = 0, i;
  fin >> n >> m;
  for( i = 0; i < m; i++ ) {
    fin >> a >> b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  for( i = 1; i <= n; i++ ) {
    if( stare[i] == 0 ) {
      nr++;
      dfs(i);
    }
  }
  fout << nr;
  return 0;
}