Cod sursa(job #2928276)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 22 octombrie 2022 17:04:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

vector<int>  v[100001];
int frcv[100001];

void dfs( int nod ){
  int i;
  if( frcv[nod] == 1 )
    return ;
  frcv[nod] = 1;
  for( i = 0 ; i < v[nod].size(); i++ )
    dfs(v[nod][i]);
}
int main()
{
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    int n , m ,i , rez = 0 , a , b ;
    in >> n >> m ;
    for( i = 0 ; i < m ; i ++ ){
      in >> a >> b;
      v[a].push_back(b);
      v[b].push_back(a);
    }
    for( i = 1; i <= n ; i ++ )
      if( frcv[i] == 0 ){
        rez++;
        dfs(i);
      }
    out << rez ;
    return 0;
}