Pagini recente » Cod sursa (job #1612156) | Cod sursa (job #775034) | Cod sursa (job #2262401) | Cod sursa (job #150321) | Cod sursa (job #1811791)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int N, M, nr;
bool viz[ 100002 ];
vector < int > Q[ 100002 ];
stack < int > st;
int main()
{ f >> N >> M;
for (int x, y, i = 1; i <= M; ++i)
f >> x >> y , Q[x].push_back(y) , Q[y].push_back(x);
for (int i = 1; i <= N; ++i)
{ if (!viz[i])
{ ++nr; st.push(i); viz[i] = true;
while(!st.empty())
{ int k = st.top(); bool ok = false;
vector < int > :: iterator it = Q[k].begin(), sf=Q[k].end();
for( ; it != sf && !ok; ++it)
if (!viz[*it])
{st.push(*it); viz[*it] = 1; ok = true;}
if (!ok) st.pop();
}
}
}
g << nr << '\n';
return 0;
}