Pagini recente » Profil MonicaVizitiu | Cod sursa (job #3121479) | Cod sursa (job #368396) | Cod sursa (job #2461129) | Cod sursa (job #1007988)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
struct nod
{
int info;
nod *urm;
};
nod *p[100005];
int n,m,viz[100005],c[100005],nr;
nod *po[100005];
inline void Citire()
{
int i,k=1,x,y,contr=1;
nod *prim,*p,*u;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
i=1;
scanf("%d%d",&x,&y);
while (i<=m)
{
if (x!=k)
k=x;
p=new nod;
p->info=y;
p->urm=NULL;
u=p;
if (i<m)
{i++;
scanf("%d%d",&x,&y);
while (x==k && contr==1)
{
prim=new nod;
prim->info=y;
prim->urm=NULL;
u->urm=prim;
u=prim;
if (i<m)
{i++;
scanf("%d%d",&x,&y);
}
else contr=0;
}
po[k]=p;
}
else {i=m+1;po[k]=p;}
}
}
inline void BreadhtFirst()
{
int i,contor,v,pr,ul;
contor=1;
while (contor<=n && contor!=-1)
{
c[1]=contor;viz[contor]=1;
pr=1;ul=1;
nod *prim;
while (pr<=ul)
{
v=c[pr];pr=pr+1;
for (prim=po[contor];prim!=NULL;prim=prim->urm)
if (viz[prim->info]==0)
{
ul=ul+1;
c[ul]=prim->info;
viz[prim->info]=1;
}
}
nr++;
contor=-1;
for (i=1;i<=n && contor==-1;i++)
if (viz[i]==0)
contor=i;
}
}
int main()
{
int i;
Citire();
BreadhtFirst();
printf("%d\n",nr);
return 0;
}