Cod sursa(job #595570)

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

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

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

void adNod(long long x,long 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 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 long i)
{
    long long 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);
    long long nr = 0,i;
    read();
    for(i = 1; i <= n; i++)
    {
        if(pus[i] == 0)
        {
            nr++;
            df(i);
        }
    }
    //afis();
    printf("%ld ",nr);
    return 0;
}