Cod sursa(job #3253621)

Utilizator DajaMihaiDaja Mihai DajaMihai Data 3 noiembrie 2024 20:42:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

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

int n, m, comp;
vector<int> v[100001];
int visited[100001];

void dfs (int nod){
  for(int i : v[nod]){
    if(!visited[i]){
      visited[i] = 1;
      dfs(i);
    }
  }
}

int main()
{
  in >> n >> m;
  for(int i = 0 ; i < m; i ++)
  {
    int a, b;
    in >> a >> b;
    if((a > 0 && a <= n) && (b > 0 && b <= n))
    {
      v[a].push_back(b);
      v[b].push_back(a);
    }
  }

  for(int i = 1; i <= n; i ++){
    if(!visited[i]){
      comp ++;
      dfs(i);
    }
  }
  out << comp;
}