Pagini recente » Cod sursa (job #1890192) | Cod sursa (job #2452284) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #202980)
Cod sursa(job #202980)
#include<stdio.h>
FILE *f,*g;
long c[100005],t[3][400005],viz[100005],n,m,i,j,nr,x,y,v;
int dfs(long k)
{ long v=c[k]; viz[k]=1;
while(t[2][v]!=0)
{ if(!viz[t[1][v]]) dfs(t[1][v]);
v=t[2][v];
}
if(!viz[t[1][v]]) dfs(t[1][v]);
return 0;
}
int main()
{ f=fopen("dfs.in","r"); g=fopen("dfs.out","w");
fscanf(f,"%ld%ld",&n,&m);
nr=1;
for(i=1;i<=m;i++)
{ fscanf(f,"%ld%ld",&x,&y);
if(!c[x])
{ while(t[1][nr]!=0) nr++;
c[x]=nr; t[1][nr]=y;
}
else
{ v=c[x];
while(t[2][v]!=0) v=t[2][v];
while(t[1][nr]!=0) nr++;
t[2][v]=nr; t[1][nr]=y;
}
}
nr=0;
for(i=1;i<=n;i++)
if(!viz[i])
{ nr++;
dfs(i);
}
fprintf(g,"%ld",nr);
fclose(g);
return 0;
}