Cod sursa(job #212217)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 4 octombrie 2008 17:31:36
Problema Parcurgere DFS - componente conexe Scor 5
Compilator c Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>

#define FIN "dfs.in"
#define FOUT "dfs.out"

#define NMAX 1015

int n,m;
int i,nr;
int viz[NMAX];
int a[NMAX][NMAX];
int x,y;

void read_data()
{
    freopen(FIN,"rt",stdin);
    scanf("%d %d", &n,&m);
    for (i=1;i<=m;++i)
          {
                scanf("%d %d", &x, &y);
                a[x][y]=a[y][x]=1;
          }
}

void DFS(int x)
{
    viz[x]=1;
    for (i=1;i<=n;++i)
         if (!viz[i] && a[x][i])
              DFS(i);
}

void solve()
{
    for (i=1;i<=n;++i)
          if (!viz[i])
              {
                    nr++;
                    DFS(i);
              }
}

void write_data()
{
    freopen(FOUT,"wt",stdout);
    printf("%d", nr);
}

int main()
{
    read_data();
    solve();
    write_data();
    return 0;
}