Cod sursa(job #900610)
Utilizator | Data | 28 februarie 2013 20:48:11 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include<stdio.h>
int a[1000][1000],v[1000],n;
void dfs(int nod)
{
int i;
v[nod]=1;
for(i=1;i<=n;i++)
if(v[i]==0&&a[nod][i]==1)
dfs(i);
}
int main()
{
int i,m,x,y,nr=0;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=1;
a[y][x]=1;
}
for(i=1;i<=n;i++)
{
if(v[i]==0)
{
dfs(i);
nr++;
}
}
printf("%d",nr);
return 0;
}