Cod sursa(job #1611718)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 februarie 2016 13:02:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

void explore_component(const int x, const vector<vector<int>>& vec, vector<bool>& e_viz){
    stack<int, vector<int>> st;
    st.push(x);
    e_viz[x] = true;

    while(!st.empty()){
        const int cur = st.top();
        st.pop();
        for(int i = 0; i < vec[cur].size(); ++i){
            const int next = vec[cur][i];
            if(!e_viz[next]){
                e_viz[next] = true;
                st.push(next);
            }
        }
    }
}

int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int n, m;
    f >> n >> m;

    vector<vector<int> > vec(n);
    for(int i = 0, a, b; i < m; ++i){
        f >> a >> b;
        --a, --b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    vector<bool> e_viz(n, false);

    int rez = 0;
    for(int i = 0; i < n; ++i){
        if(!e_viz[i]){
            ++rez;
            explore_component(i, vec, e_viz);
        }
    }

    g << rez << '\n';

    return 0;
}