Pagini recente » Cod sursa (job #240137) | Cod sursa (job #1622238) | Cod sursa (job #637776) | Cod sursa (job #648719) | Cod sursa (job #328346)
Cod sursa(job #328346)
#include<stdio.h>
#define Nmx 100001
int n,m,viz[Nmx],qu[Nmx];
struct nod
{
int inf;
nod *urm;
};
nod *G[Nmx];
void insert(int x,int y)
{
nod *aux;
aux=new nod;
aux->urm=G[x];
aux->inf=y;
G[x]=aux;
}
void citire()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
insert(x,y);
insert(y,x);
}
}
void dfs()
{
int nr=0;
for(int i=1;i<=n;i++)
{
if(viz[i]==0)
{
nr++;
int st,dr;
st=dr=1;
qu[1]=i;
viz[i]=1;
while(st<=dr)
{
for(nod *p=G[qu[st]];p!=NULL;p=p->urm)
{
if(!viz[p->inf])
{
viz[p->inf]=1;
qu[++dr]=p->inf;
}
}
++st;
}
}
}
printf("%d\n",nr);
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
citire();
dfs();
return 0;
}