Cod sursa(job #3295380)

Utilizator cristab25Cristiana Tabacaru cristab25 Data 4 mai 2025 21:15:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>

using namespace std;

class Graph {
    public:
    unordered_map <int, vector<int> > adj_list;
    void add_egde (int n1, int n2) {
        adj_list[n1].push_back(n2);
        adj_list[n2].push_back(n1);
    }

    int dfs(int nodes_number) {
        
        vector <int> parents (nodes_number + 1, -1);
        vector <int> start_time (nodes_number + 1, 0);
        vector <int> end_time (nodes_number + 1, 0);

        int comp_conexe = 0;

        int timestamp = 0;
        for (int i = 1; i <= nodes_number; i++) {
            if (parents[i] == -1) {
                // cout<< "incep parcurgerea cu nodul: "<< i << '\n';
                comp_conexe++;
                parents[i] = i;
                dfs_recursive(i, parents, start_time, end_time, timestamp);
            }
        }

        // cout<<'\n';

        // for (int i = 1; i < start_time.size(); i++) {
        //     cout<< "Pentru nodul "<< i<< " start : " << start_time[i] << " end: "<< end_time[i] << '\n';
        // }

        // cout << '\n' << comp_conexe << '\n';
        return comp_conexe;

    }

    void dfs_recursive (int root, vector<int> &parents, vector<int> &start, vector<int> &end, int &timestamp) {
        timestamp++;
        start[root] = timestamp;

        for (auto adj_node : adj_list[root]) {
            if (parents[adj_node] == -1) {
                parents[adj_node] = root;
                dfs_recursive(adj_node, parents, start, end, timestamp);
            }
        }

        timestamp++;
        end[root] = timestamp;
    }


};

int main() {
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    
    
    Graph g;
    
    int nodes, edges;
    fin >> nodes >> edges;

    int n1, n2;
    while (fin >> n1 && fin >> n2) {
        g.add_egde(n1, n2);
        // cout<<n1<< " "<<n2<<'\n';
    }

    fout << g.dfs(nodes);
    return 0;
}