Cod sursa(job #2413352)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 23 aprilie 2019 12:37:12
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m, nr;
bool *viz;

vector<vector<int>> a;

void dfs( int x )
{
    int i, y;
    viz[x] = true;
    for(i = 0; i < a[x].size(); i++)
    {
        y = a[x][i];
        if( !viz[y] )
            dfs( y );
    }
    ++nr;
}

int main ( ){

  int i, x, y;

  in >> n >> m;

  viz = new bool [n + 2];

  for ( i = 0; i <= n; i++ ){
    a.push_back ( vector<int> ());
    viz[i] = false;
  }

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

  dfs ( 1 );

  out << nr;

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

  delete viz;

  return 0;
}