Cod sursa(job #631950)
Utilizator | Stefan Lache StefanLache | Data | 9 noiembrie 2011 22:34:23 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include<stdio.h>
int N,M,A[1000][1000],s[1000],nr;
void constr()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&N,&M);
int i,a,b;
for(i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
A[a][b]=A[b][a]=1;
}
}
void DFS(int nod)
{
int i;
s[nod]=1;
for(i=1;i<=N;i++)
if(A[nod][i]==1&&s[i]==0)
DFS(i);
}
int main()
{
constr();int i;
for(i=1;i<=N;i++)
if(!s[i])
{nr++;DFS(i);}
printf("%d",nr);
return 0;
}