Pagini recente » Cod sursa (job #1508260) | Cod sursa (job #982042) | Cod sursa (job #1076628) | Cod sursa (job #1541863) | Cod sursa (job #607917)
Cod sursa(job #607917)
#include <iostream>
#include <stdio.h>
#define max 100001
using namespace std;
struct art{int val; art *urm; }*q;
int main()
{
FILE *f,*g;
art *p[max],*aux;
int c[max],pr,u,nc,a,b,viz[max],m,n,i;
f=fopen("dfs.in","r");
g=fopen("dfs.out","w");
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=m;i++)
{fscanf(f,"%d %d",&a,&b);
aux=new art;
aux->val=b;
aux->urm=p[a];
p[a]=aux;
}
for(i=1;i<=n;i++)viz[i]=0;
do
{
a=1;
while(viz[a]==1&&a<=n) a++;
viz[a]=1;
pr=1;u=1;
c[1]=a;
while(pr<=u)
{aux=p[c[pr]];
while(aux!=NULL)
{if(viz[aux->val]==0){viz[aux->val]=1; u++; c[u]=aux->val;}
aux=aux->urm;
}
pr++;
}
nc++;
}
while(a<=n);
nc=nc-1;
fprintf(g,"%d",nc);
fclose(f);
fclose(g);
return 0;
}