Mai intai trebuie sa te autentifici.
Cod sursa(job #873771)
| Utilizator | 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';
}
