Pagini recente » Cod sursa (job #3291116) | Cod sursa (job #2905001) | Borderou de evaluare (job #1004041) | Cod sursa (job #2650365) | Cod sursa (job #212590)
Cod sursa(job #212590)
#include<stdio.h>
int li[3][200001],nr,fin,parc,st,i,f[100001],j,n,m,ver[100001],coada[100001];
void bf(int nod)
{ st=1;
fin=2;
coada[st]=nod;
f[nod]=nr;
while(st<=fin)
{ parc=ver[coada[st]];
while(parc!=0)
{ if(f[li[1][parc]]==0)
{ coada[fin]=li[1][parc];
f[li[1][parc]]=nr;
fin++; }
parc=li[2][parc];
}
st++;
}
}
int main()
{freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int k=1;
scanf("%d%d",&n,&m);
scanf("%d%d",&i,&j);
while(i!=0&&j!=0)
{ li[1][k]=j;
li[2][k]=ver[i];
ver[i]=k;
k++;
li[1][k]=i;
li[2][k]=ver[j];
ver[j]=k;
k++;
i=0; j=0;
scanf("%d%d",&i,&j);
}
for(i=1;i<=n;i++)
{ if(f[i]==0)
{ nr++;
bf(i); }
}
printf("%d",nr);
return 0;
}