Cod sursa(job #2425239)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 24 mai 2019 17:13:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int N = 100005;

vector <int> mat[N];
vector <bool> viz(N, 0);


void dfs( int x, int n ){
  if ( mat[x].empty() )
    return;
  viz[x] = 1;
  for ( auto i : mat[x] )
    if ( ! viz[i] )
      dfs(i, n);
}

int main() {

  int m, n, i, nr = 0, x, y;

  //ifstream in ("date.in");
  ifstream in("dfs.in");
  in >> n >> m;
  for ( i = 1; i <= m; i++ ){
    in >> x >> y;
    mat[x].push_back (y);
    mat[y].push_back (x);
  }
  in.close();

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

  //ofstream out ("date.out");
  ofstream out ("dfs.out");
  out << nr;
  out.close();

  return 0;
}