Pagini recente » Cod sursa (job #2953006) | Cod sursa (job #2959700) | Cod sursa (job #935989) | Cod sursa (job #2242267) | Cod sursa (job #873771)
Cod sursa(job #873771)
#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';
}