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