Cod sursa(job #2413366)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 23 aprilie 2019 12:43:16
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 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 );
    }
}

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);
  }

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

  out << nr;

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

  delete viz;

  return 0;
}