Pagini recente » Cod sursa (job #2144456) | Cod sursa (job #1312347) | Cod sursa (job #1334306) | Cod sursa (job #1438798) | Cod sursa (job #295157)
Cod sursa(job #295157)
#include<stdio.h>
int viz[100000];
long t[4][400000],c[100000],m,liber,i,x,y,p,n,nr;
FILE *f,*g;
void df(long k)
{ long p; viz[k]=1;
p=c[k];
while(p!=0)
{ if(!viz[t[1][p]]) df(t[1][p]);
p=t[2][p];
}
}
int main()
{ f=fopen("dfs.in","r"); g=fopen("dfs.out","w");
fscanf(f,"%ld%ld",&n,&m);
liber=1;
for(i=1;i<=m;i++)
{ fscanf(f,"%ld%ld",&x,&y);
if(c[x]==0) { c[x]=liber; t[1][liber]=y; liber++; }
else
{ p=c[x];
while(t[2][p]!=0) p=t[2][p]; t[2][p]=liber; t[1][liber]=y; liber++;
}
if(c[y]==0) { c[y]=liber; t[1][liber]=x; liber++; }
else
{ p=c[y];
while(t[2][p]!=0) p=t[2][p]; t[2][p]=liber; t[1][liber]=x; liber++;
}
}
nr=0;
for(i=1;i<=n;i++) if(!viz[i])
{ nr++; df(i); }
fprintf(g,"%ld",nr);
fclose(g);
return 0;
}