Cod sursa(job #3363530)

Utilizator MesterelllMester Darius Mesterelll Data 18 august 2026 20:22:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

unordered_map <int, vector<int>>lista; //lista de adiacenta

int n, m; //nr de noduri si muchii
bool used[100001];
int cnt_vizitat;

void dfs(int k){
    //cout<<k<<' ';
    used[k]=true;
    ++cnt_vizitat;
	for(auto nod : lista[k]){
        if (used[nod]==false)
            dfs(nod);
    }
}

bool mai_avem_nevizitate(){
    return cnt_vizitat < n;
}

int urmatorul_nevizitat(){
    for (int i=1; i<=n; ++i)
        if (used[i]==false)
            return i;
}

int main(){
  	ifstream fin("dfs.in");
  	ofstream fout("dfs.out");
  	fin>>n>>m;
  	int a,b;
  	for(int i=0; i<m; ++i){
      	fin>>a>>b;
      	lista[a].push_back(b);
      	lista[b].push_back(a);
    }
    int cnt_conexe=0;
    for (int i=1; i<=n; ++i)
        if (used[i]==false){
            dfs(i);
            ++cnt_conexe;
        }
    fout<<cnt_conexe;
}