Pagini recente » Cod sursa (job #3255472) | Cod sursa (job #3258319) | Cod sursa (job #1380080) | Cod sursa (job #3274979) | Cod sursa (job #2549831)
#include <bits/stdc++.h>
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int n,m,nr,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]=1;
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'; g.close(); f.close(); return 0;
}