Cod sursa(job #283221)

Utilizator DraStiKDragos Oprica DraStiK Data 18 martie 2009 21:04:16
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#define DIM 1005
int a[DIM][DIM],uz[DIM];
int n,m,nrt;
void read ()
{
    int i,x,y;
    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 nod)
{
    int i;
    uz[nod]=1;
    for (i=1; i<=n; ++i)
        if (!uz[i] && a[i][nod])
            dfs (i);
}
void solve ()
{
    int i;
    for (i=1; i<=n; ++i)
        if (!uz[i])
        {
            ++nrt;
            dfs (i);
        }
    printf ("%d",nrt);
}
int main ()
{
    freopen ("dfs.in","r",stdin);
    freopen ("dfs.out","w",stdout);
    read ();
    solve ();
    return 0;
}