Cod sursa(job #3243417)

Utilizator ReithoferCarlaReithofer Carla ReithoferCarla Data 18 septembrie 2024 16:35:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
using namespace std;

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

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

void dfs(int nod_crt) {
    v_caracteristic[nod_crt] = 1;
    for(auto noduri:v[nod_crt])
        if(!v_caracteristic[noduri])
            dfs(noduri);
}
int main() {

    int n, m;
    cin >> n >> m;

    v.resize(n+1);

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int nr_comp=0;

    for (int i = 1; i <= n; i++)
        if(!v_caracteristic[i]) {
            nr_comp++;
            dfs(i);
        }

    cout << nr_comp;
    return 0;
}