Cod sursa(job #3337204)

Utilizator Mariusq17Ignat Marius Florentin Mariusq17 Data 27 ianuarie 2026 01:08:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
// #include <iostream>
// #include <fstream>
// #include <vector>
#include <bits/stdc++.h>

using namespace std;

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

void dfs(int startNode, vector<vector<int>>& adj, vector<int>& visited) {
    visited[startNode] = 1;

    // for(int i = ; i < adj[startNode].size(); i++) {
    //     if(!visited[adj[startNode][i]]) {
    //         dfs(i, adj, visited);
    //     }
    // }

    for(int vecin : adj[startNode]) {
        if(!visited[vecin]) {
            dfs(vecin, adj, visited);
        }
    }
}

int cmpConex(vector<vector<int>>& adj) {
    int n = adj.size();
    int nrConex = 0;

    vector<int> visited(n, 0);

    for(int i = 1; i < n; i++) {
        if(!visited[i]) {
            nrConex++;
            dfs(i, adj, visited);
        }
    }

    return nrConex;
}

int main() {
    int N, M;
    fin >> N >> M;

    // Initializare liste de adiacenta si vector vizitat
    vector<vector<int>> adj(N + 1);

    // Citire muchii
    for(int i = 0; i < M; i++) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x); // Graf neorientat
    }

    int conex = cmpConex(adj);
    fout << conex;
    return 0;
}