Pagini recente » Cod sursa (job #1055559) | Cod sursa (job #3167849) | Cod sursa (job #3224520) | Cod sursa (job #905848) | Cod sursa (job #873730)
Cod sursa(job #873730)
#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].push_back(b);
}
std::vector<bool> visited(N,false);
std::stack<unsigned> st;
unsigned v=0,c=0;
while(v<N){
c++;
unsigned S=0;
while(visited[S]) ++S;
st.push(S); visited[S]=true; ++v;
while(!st.empty()){
if(liste[st.top()].empty()) st.pop();
else{
unsigned M=liste[st.top()].front();
if(!visited[M]){ visited[M]=true; ++v; st.push(M); }
liste[st.top()].pop_front();
}
}
}
fout<<c<<'\n';
}