Cod sursa(job #212224)
| Utilizator | Data | 4 octombrie 2008 17:43:20 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 0 |
| Compilator | c | Status | done |
| Runda | Arhiva educationala | Marime | 0.95 kb |
#include <stdio.h>
#define FIN "dfs.in"
#define FOUT "dfs.out"
#define NMAX 7005
int n,m;
int nr;
int viz[NMAX];
int a[NMAX][NMAX];
int x,y;
void read_data()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d %d",&n,&m);
int i;
for (i=1;i<=m;++i)
{
scanf("%d %d",&x,&y);
a[x][y]=a[y][x]=1;
}
}
void DFS(int x)
{
int i;
viz[x]=1;
for (i=1;i<=n;++i)
if (!viz[i] && a[x][i])
DFS(i);
}
void solve()
{
int i;
for (i=1;i<=n;++i)
if (!viz[i])
{
nr++;
DFS(i);
}
}
int main()
{
read_data();
solve();
printf("%d", nr);
return 0;
}
