Pagini recente » Cod sursa (job #2457574) | Cod sursa (job #1822372) | Cod sursa (job #1371384) | Cod sursa (job #1861097) | Cod sursa (job #1267869)
#include <stdio.h>
using namespace std;
#define MAX 200000
int lst[100000];
int urm[MAX],vf[MAX];
int nr,q[100000],viz[100000];
int p=1, u=0;
void adauga(int x,int y)
{
vf[++nr]=y;
urm[nr]=lst[x];
lst[x]=nr;
}
void dfs(int x0)
{
int x,poz,y;
q[++u]=x0;
viz[x0]=1;
while(p<=u)
{
x=q[p++];
poz=lst[x];
while(poz!=0)
{
y=vf[poz];
if(viz[y]==0)
viz[y]=1;
poz=urm[poz];
}
}
}
int main()
{
FILE *fin,*fout;
fin=fopen("dfs.in","r");
fout=fopen("dfs.out","w");
int i,j,cnt=0,n,m,x,y;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&x,&y);
adauga(x,y);
}
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
cnt++;
dfs(i);
}
}
fprintf(fout,"%d",cnt);
return 0;
}