Pagini recente » Cod sursa (job #2701986) | Cod sursa (job #2881511) | Cod sursa (job #794410) | Cod sursa (job #1820000) | Cod sursa (job #277665)
Cod sursa(job #277665)
#include<stdio.h>
#include<string.h>
#define Nmax 100001
int n,nr;
struct nod
{
int info;
nod *urm;
};
typedef nod *Lista;
Lista L[Nmax],U[Nmax];
void Insert(Lista &prim,Lista p,int x)
{
Lista q=new nod;
q->info=x;
if(prim) { q->urm=p->urm; p->urm=q;}
else { q->urm=prim; prim=q;}
}
void DFS();
int main()
{int m,i,x,y;
freopen("dfs.in","rt",stdin);
freopen("dfs.out","wt",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=m;++i)
{scanf("%d %d",&x,&y);
if(L[x]) Insert(L[x],U[x],y),U[x]=U[x]->urm;
else Insert(L[x],NULL,y),U[x]=L[x];
if(L[y]) Insert(L[y],U[y],x),U[y]=U[y]->urm;
else Insert(L[y],NULL,x),U[y]=L[y];
}
DFS();
printf("%d",nr);
return 0;
}
bool uz[Nmax];
void DFS()
{
Lista p;
int v[Nmax],st,x,i;
for(i=1;i<=n;++i)
if(!uz[i])
{st=1; v[1]=i; uz[i]=1;
while(st)
{
x=v[st--];
for(p=L[x];p;p=p->urm)
if(!uz[p->info]) v[++st]=p->info,uz[p->info]=1;
}
nr++;
}
}