Cod sursa(job #2796904)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 8 noiembrie 2021 23:28:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
// Mihai Priboi

#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 100000

vector<int> muchii[MAXN + 1];

bool noduri[MAXN + 1];

void fill( int nod ) {
  int i;
  noduri[nod] = true;
  for( i = 0; i < muchii[nod].size(); i++ )
    if( !noduri[muchii[nod][i]] )
      fill( muchii[nod][i] );
}

int main() {
  FILE *fin, *fout;
  int n, m, i, x, y, cnt;

  fin = fopen( "dfs.in", "r" );

  fscanf( fin, "%d%d", &n, &m );
  for( i = 0; i < m; i++ ) {
    fscanf( fin, "%d%d", &x, &y );
    muchii[x].push_back(y);
    muchii[y].push_back(x);
  }

  fclose( fin );

  cnt = 0;
  for( i = 1; i <= n; i++ ) {
    if( !noduri[i] ) {
      cnt++;
      fill(i);
    }
  }


  fout = fopen( "dfs.out", "w" );
  fprintf( fout, "%d", cnt );
  fclose( fout );
  return 0;
}