Pagini recente » Cod sursa (job #2095487) | Cod sursa (job #604087) | Cod sursa (job #173263) | Cod sursa (job #1517080) | Cod sursa (job #153476)
Cod sursa(job #153476)
#include<fstream.h>
#include<stdlib.h>
#define dim 10001
int *a[dim],viz[dim],c[dim];
unsigned long n,i,m,j,prim,ultim,x,y;
int main()
{ifstream f("dfs.in");
ofstream g("dfs.out");
f>>n>>m;
for(i=1;i<=n;i++)
{a[i]=(int*)realloc(a[i],sizeof(int));
a[i][0]=0;
}
for(i=1;i<=m;i++)
{f>>x>>y;
a[x][0]++;
a[x]=(int*)realloc(a[x],a[x][0]*sizeof(int));
a[x][a[x][0]]=y;
a[y][0]++;
a[y]=(int*)realloc(a[y],a[y][0]*sizeof(int));
a[y][a[y][0]]=x;
}
f.close();
unsigned long cont=0;
for(i=1;i<=n;i++)
if(!viz[i])
{cont++;
c[0]=i;
viz[i]=1;
prim=ultim=0;
while(prim<=ultim)
{x=c[prim++];
for(j=1;j<=a[x][0];j++)
if(!viz[a[x][j]])
{viz[a[x][j]]=1;
c[++ultim]=a[x][j];
}
}
}
g<<cont<<'\n';
g.close();
return 0;
}