Cod sursa(job #595567)

Utilizator MirceampMuresan Mircea Paul Mirceamp Data 13 iunie 2011 03:49:49
Problema Parcurgere DFS - componente conexe Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>
#define Max 1000000

typedef struct node
{
    int info;
    struct node *next;
}nod;
int n,m;
nod *a[Max];
int pus[Max];
void adNod(int x, int y)
{
    nod *p,*q;

    q = (nod *)malloc(sizeof(nod));

    q->info = y;
    q->next = NULL;

    if(a[x] == NULL)
    a[x] = q;
    else
    {
        p = a[x];
        while(p->next != NULL)
        p = p->next;
        p->next = q;
    }

}
void read()
{
    int x,y,i;

    freopen("dfs.in","rt",stdin);

    scanf("%d %d",&n,&m);

    for(i = 1; i <= m; i++)
    {
        scanf("%d %d",&x,&y);
        adNod(x,y);
        adNod(y,x);

    }

}
/*void afis()
{
    freopen("date.out","wt",stdout);

    nod *p;
    for(int i = 1; i <= n; i++)
    {
        p = a[i];
        printf("%d ",i);
        while(p != NULL)
        {
            printf("%d ",p->info);
            p = p->next;
        }
        printf("\n");
    }
}*/
void df(int i)
{
    int sursa;
    nod *p;

            pus[i] = 1;
            p = a[i];
        if(p != NULL)
        {

        while(p->next != NULL)
        {
           sursa = p->info;
           df(sursa);
            p = p->next;
        }
        if(!pus[p->info])
        df(p->info);
        }
}
int main()
{
    freopen("dfs.out","wt",stdout);
    int nr = 0,i;
    read();
    for(i = 1; i <= n; i++)
    {
        if(pus[i] == 0)
        {
            nr++;
            df(i);
        }
    }
    //afis();
    printf("%d ",nr);
    return 0;
}