Pagini recente » Cod sursa (job #1685491) | Cod sursa (job #3251857) | Cod sursa (job #2433144) | Cod sursa (job #2722982) | Cod sursa (job #237465)
Cod sursa(job #237465)
#include<stdio.h>
#include<stdlib.h>
int *a[100001],nr,n,m,i,x,y,s,q[100001],fol[100001];
void citire();
void bf(int);
void afisare();
int main(){
citire();
for (int i=1;i<=n;i++)
if (!fol[i])
bf(i),nr++;
afisare();
return 0;
}
void citire(){
int i;
freopen("dfs.in","r",stdin);
scanf("%d %d ",&n,&m);
for (i=1;i<=n;i++){
a[i]=(int*)malloc(sizeof(int));
a[i][0]=0;
}
for (i=1;i<=m;i++){
scanf("%d %d", &x,&y);
a[x][0]++;
a[x]=(int*) realloc(a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
}
}
void bf(int w){
int i,j,u;
q[0]=w;
fol[w]=1;
for (i=0,u=0;i<=u;i++){
x=q[i];
for (j=1;j<=a[x][0];j++)
if (!fol[a[x][j]]){
fol[a[x][j]]=1;
q[++u]=a[x][j];
}
}
}
void afisare(){
freopen("dfs.out","w",stdout);
printf("%d\n",nr);
}