Mai intai trebuie sa te autentifici.
Cod sursa(job #1036254)
Utilizator | Data | 19 noiembrie 2013 08:55:23 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.88 kb |
#include<stdio.h>
struct aaaa
{
int vrf,urm;
};
aaaa a[400003];
int lista [100004],viz[100004],nr,poz,n,m,i;
void adauga(int x,int y)
{
a[nr].vrf=y;
a[nr].urm=lista[x];
lista[x]=nr;
nr++;
}
void parc(int k)
{
int poz=lista[k];
viz[k]=1;
while(poz!=-1)
{
int y=a[poz].vrf;
if(viz[y]==0)
parc(y);
poz=a[poz].urm;
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
for(i=1;i<=n;i++)
lista[i]=-1;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
adauga(x,y);
adauga(y,x);
}
int s=0;
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
s++;
parc(i);
}
}
printf("%d",s);
return 0;
}