Cod sursa(job #595653)

Utilizator MirceampMuresan Mircea Paul Mirceamp Data 13 iunie 2011 14:58:25
Problema Cautare binara Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>
#define Max 100001

typedef struct node
{
    long info;
    struct node *next;
}nod;

long n,m;
nod *a[Max];
long pus[Max];

void adNod(long x,long 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()
{
    long x,y,i;

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

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

    for(i = 1; i <= m; i++)
    {
        scanf("%ld %ld",&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(long i)
{
    long sursa;
    nod *p;

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

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