Cod sursa(job #873771)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 7 februarie 2013 16:55:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <list>
#include <vector>
#include <stack>

int main(){
    std::ifstream fin("dfs.in");
    std::ofstream fout("dfs.out");

    unsigned N,M;
    fin>>N>>M;
    std::vector< std::list<unsigned> > liste(N);
    for(unsigned i=0;i<M;++i){
        unsigned a,b; fin>>a>>b;
        liste[a-1].push_back(b-1); liste[b-1].push_back(a-1);
    }

    std::vector<bool> visited(N,false);
    std::stack<unsigned> st;

    unsigned c=0,S=0;
    while(S<N){
        c++;
        while(visited[S]) ++S;
        st.push(S); visited[S]=true;

        while(!st.empty()){
            if(liste[st.top()].empty()) st.pop();
            else{
                unsigned M=liste[st.top()].front();
                liste[st.top()].pop_front();
                if(!visited[M]){ visited[M]=true; st.push(M); }
            }
        }
        while(visited[S]) ++S;
    }
    fout<<c<<'\n';
}