Pagini recente » Istoria paginii runda/spad/clasament | Cod sursa (job #1602664) | Cod sursa (job #2473990) | Cod sursa (job #2732648) | Cod sursa (job #2841518)
#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<<endl;
f.close();
g.close();
return 0;
}