Cod sursa(job #3237541)

Utilizator tsg38Tsg Tsg tsg38 Data 9 iulie 2024 21:23:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e5 + 1;

vector<int> G[DIM];
bool viz[DIM];

void dfs( int u ) {
  viz[u] = true;
  for ( auto v : G[u] ) {
	if ( !viz[v] ) dfs(v);
  }
}

int main() {
  int n, m, u, v;

  fin >> n >> m;
  while ( m-- ) {
	fin >> u >> v;
    G[u].push_back(v);
	G[v].push_back(u);
  }
  int res = 0;
  for ( int i = 1; i <= n; ++i ) {
	if ( !viz[i] ) {
      dfs(i);
	  ++res;
	}
  }
  fout << res;
  fin.close();
  fout.close();
  return 0;
}