Pagini recente » Cod sursa (job #3121308) | Cod sursa (job #51298) | Cod sursa (job #831697) | Cod sursa (job #2441445) | Cod sursa (job #159088)
Cod sursa(job #159088)
#include <stdio.h>
struct nod{
nod *urm;
long nd;
}*p[100000],*aux;
long n,m,i,x,y,marc[100000],nmarc,n_con;
void dfs(long nxd)
{ nod *aux=p[nxd];
while (aux){
while(aux) {if (!marc[aux->nd]) break; aux=aux->urm;}
if (aux!=NULL) {
marc[aux->nd]=1; nmarc++;
dfs(aux->nd);
}}
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%ld%ld", &n,&m);
for(i=0;i<m;i++){
scanf("%ld%ld",&x,&y);
aux=new nod;
aux->urm=p[x];
aux->nd=y;
p[x]=aux;
}
while(nmarc<n){
for(i=1;i<=n;i++) if (marc[i]==0) break;
nmarc++;
dfs(i);marc[i]=1;n_con++;
}
printf("%ld",n_con);
/* for(i=1;i<=n;i++){
printf("%ld ",i);
aux=p[i];
while (aux)
{printf("%ld ",aux->nd), aux=aux->urm;}
printf("\n");
}
*/
return 0;
}