Cod sursa(job #247309)

Utilizator hasegandaniHasegan Daniel hasegandani Data 22 ianuarie 2009 19:42:46
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>

#define nmax 1001

int viz[nmax],n;

struct nod
{
    int info;
    nod *adr;
};

nod *lista[nmax];

void add(nod *&,int);
void dfs(int);

int main()
{
    int a,b,m,x=0;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
            {
            scanf("%d%d",&a,&b);
            add(lista[a],b);
            add(lista[b],a);
            }
    for(int i=1;i<=n;++i)
            if (!viz[i])
               {
               ++x;
               ++viz[i];
               dfs(i);
               }
    printf("%d\n",x);
    return 0;
}

void add(nod *&inc,int inf)
{
    if (inc)
        {
        nod *p=new nod;
        p->adr=inc;
        p->info=inf;
        inc=p;
        }
    else
        {
        nod *p=new nod;
        p->info=inf;
        inc=p;
        }
}

void dfs(int k)
{
     nod *p=lista[k];
     for(;p;p=p->adr)
        {
        int x=p->info;
        if (!viz[x] && x)
                         {
                         viz[x]=1;
                         dfs(x);
                         }
        }
}