Cod sursa(job #1734576)

Utilizator ataegasMr. HHHHHH ataegas Data 27 iulie 2016 18:10:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#define nmax 100001
using namespace std;

void get_data (int &n_nodes, int &n_edges, vector <int> edges[nmax]){
    ifstream fin ("dfs.in");
    fin >> n_nodes >> n_edges;
    for (int i = 1; i <= n_edges; i++){
        int node_1, node_2;
        fin >> node_1 >> node_2;
        edges[node_1].push_back (node_2);
        edges[node_2].push_back (node_1);
    }
}

void dfs (int current_node, vector <int> edges[nmax], bool seen[nmax]){
    seen[current_node] = true;
    for (auto x : edges[current_node])
        if (!seen[x])
            dfs (x, edges, seen);
}

void print_data (int n_nodes, vector <int> edges[nmax]){
    ofstream fout ("dfs.out");
    bool seen[nmax];
    for (int i = 1; i <= n_nodes; i++)
        seen[i] = false;
    int n_components = 0;
    for (int i = 1; i <= n_nodes; i++)
        if (!seen[i]){
            dfs (i, edges, seen);
            n_components ++;
        }
    fout << n_components;
}

int main(){
    int n_nodes, n_edges;
    vector <int> edges[nmax];
    get_data (n_nodes, n_edges, edges);
    print_data (n_nodes, edges);
}