Pagini recente » Cod sursa (job #2452352) | Cod sursa (job #2326979) | Cod sursa (job #965976) | Cod sursa (job #177048) | Cod sursa (job #359668)
Cod sursa(job #359668)
#include<stdio.h>
#define M 10000
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
long n,m;
long viz[M],a[M][M];
void citire()
{
long i,x,y;
fscanf(f,"%ld%ld",&n,&m);
for(i=1;i<=m;i++)
{fscanf(f,"%ld%ld",&x,&y);
a[x][y]=a[y][x]=1;
}
for(i=1;i<=n;i++)
viz[i]=-1;
fclose(f);
}
void dfs(long nod,long nr)
{
long i,c[M*10],p,u;
p=u=1;
viz[nod]=nr;
c[p]=nod;
while(p<=u)
{
nod=c[p];
for(i=1;i<=n;i++)
if(a[nod][i]==1 && viz[i]==-1) {u++;
c[u]=i;
viz[i]=nr;}
p++;
}
}
int main()
{
citire();
long nr,i, nod;
nr=nod=1;
dfs(nod,nr);
int ok=1;
while(ok)
{
ok=0;
for(i=1;i<=n;i++)
if(viz[i]==-1) {nr++;
nod=i;
ok=1;
dfs(nod,nr);}
}
fprintf(g,"%ld\n",nr);
fclose(g);
return 0;
}