Pagini recente » Cod sursa (job #817014) | Cod sursa (job #1011553) | Cod sursa (job #484934) | Cod sursa (job #2812149) | Cod sursa (job #574482)
Cod sursa(job #574482)
#include<fstream>
#include<stack>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,a,b,c,minim,w,y;
struct nod
{ int nr;
nod *urm;} *v[100005],*p;
char viz[100005];
stack<int> st;
int main()
{
int i;
f>>n>>m;
for(i=0;i<m;++i)
{ f>>a>>b;
p=new nod;
p->nr=b;
p->urm=v[a];
v[a]=p;
p=new nod;
p->nr=a;
p->urm=v[b];
v[b]=p;
}
minim=1;
while(minim<=n)
{ viz[minim]='1';
++c;
st.push(minim);
while(!st.empty())
if(v[st.top()])
{ y=st.top();
w=v[y]->nr;
viz[w]='1';
st.push(w);
v[y]=v[y]->urm;
}
else st.pop();
while(viz[minim]) ++minim;
}
g<<c<<'\n';
f.close(); g.close();
return 0;
}