Cod sursa(job #3297377)

Utilizator Arhiva_Educationala_2Arhiva Educationala doi Arhiva_Educationala_2 Data 22 mai 2025 15:50:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <stdio.h>
#include <vector>

const int MAXN = 5e5;
int viz[MAXN];
std::vector<int> adj[MAXN];

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

int main() {
  FILE *fin = fopen( "dfs.in", "r" );
  FILE *fout = fopen( "dfs.out", "w" );

  int n, m;
  fscanf( fin, "%d%d", &n, &m );

  for( int i = 0; i < m; i++ ){
    int a, b;
    fscanf( fin, "%d%d", &a, &b );
    a--; b--;

    adj[a].push_back( b );
    adj[b].push_back( a );
  }

  int ncomp = 0;
  for( int i = 0; i < n; i++ )
    if( !viz[i] ){
      ncomp++;
      dfs( i );
    }

  fprintf( fout, "%d\n", ncomp );
  fclose( fin );
  fclose( fout );
  return 0;
}