Mai intai trebuie sa te autentifici.
Cod sursa(job #1267864)
Utilizator | Data | 20 noiembrie 2014 13:24:08 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 5 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.88 kb |
#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;
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,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;
}