Cod sursa(job #3334999)

Utilizator Niku69Niku Vasile Niku69 Data 21 ianuarie 2026 01:56:44
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <stack>

int main()
{
    int n, m;
    std::vector<std::vector<int>> la;
    std::ifstream in("dfs.in");
    in >> n, m;
    for (int i = 0; i < n; i ++) {
        la.push_back(std::vector<int>());
    }
    for (int i = 0; i < m; i ++) {
        int x, y;
     	in >> x >> y;
        x --;
        y --;
        la[x].push_back(y);
    }
    in.close();
    std::vector<bool> este_parcurs(n, false);
    int nr_comp_conexe = 0;
    for (int i = 0; i < n; i ++) {
        if (este_parcurs[i]) {
            continue;
        }
        nr_comp_conexe ++;
        std::stack<int> s;
        s.push(i);
        este_parcurs[i] = true;
        while (!s.empty()) {
            int act = s.top();
            s.pop();
            for (auto vec: la[act]) {
                if (este_parcurs[vec]) {
                    continue;
                }
                este_parcurs[vec] = true;
                s.push(vec);
            }
        }
    }
    std::ofstream out("dfs.out");
    out << nr_comp_conexe;
    out.close();
        
    return 0;
}