Pagini recente » Cod sursa (job #675813) | Cod sursa (job #1237875) | Cod sursa (job #1269346) | Cod sursa (job #2180812) | Cod sursa (job #974777)
Cod sursa(job #974777)
#include <stdio.h>
#define Nmax 100002
using namespace std;
int n,m,c;
int viz[Nmax];
struct graf
{
int v;
graf *adr;
};
graf *g[Nmax];
void add(int v1,int v2)
{
graf *p;
p=new graf;
p->v=v2;
p->adr=g[v1];
g[v1]=p;
}
void citire()
{
int i,v1,v2;
scanf("%d %d",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d %d",&v1,&v2);
add(v1,v2);
add(v2,v1);
}
}
void dfs()
{
int i,st[Nmax],s,ok;
graf *p;
for(i=1;i<=n;++i)
if(viz[i]==0)
{
++c;
st[1]=i;
s=1;
viz[i]=1;
while(s>0)
{
ok=0;
for(p=g[st[s]];p;p=p->adr)
if(viz[p->v]==0)
{
++s;
st[s]=p->v;
viz[p->v]=1;
ok=1;
break;
}
if(ok==0)
--s;
}
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
citire();
dfs();
printf("%d\n",c);
fclose(stdin);
fclose(stdout);
return 0;
}