Cod sursa(job #2413396)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 23 aprilie 2019 13:09:22
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m, nr;
vector <bool> viz;

vector <vector <int>> a;

void dfs ( int x )
{
    viz[x] = true;
    if ( a[x].empty() )
      return ;
    for( auto i : a[x] )
    {
        if( !viz[i] )
            dfs( i );
    }
}

int main ( ){

  int i, x, y;
  in >> n >> m;

  a = vector<vector<int>> (n + 2);
  viz = vector <bool> ( n + 2);

  for ( i = 0; i < m ; i++ ){
    in >> x >> y;
    a[x].push_back(y);
  }

  for ( i = 1; i <= n; i++ )
    if ( not viz[i] ){
        dfs ( i );
        nr++;
      }

  out << nr;

  in.close();
  out.close();

  return 0;
}