Cod sursa(job #534980)

Utilizator sunt_emoSunt emo sunt_emo Data 16 februarie 2011 17:26:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct cell list;

typedef struct cell
{
    int data;
    list *next;
} cell;

void parse (list**,list**,int);

int main ()
{
    FILE *in=fopen ("dfs.in","r");
    FILE *out=fopen ("dfs.out","w");
    list *a[100001],*b[100001];
    int i,n,m,x,y,nr=0,c[100001];
    fscanf (in,"%d%d",&n,&m);
    for (i=1; i<=n; i++) b[i]=NULL;
    for (i=0; i<m; i++)
    {
        fscanf (in,"%d%d",&x,&y);
        if (b[x])
        {
            a[x]->next=(list*) malloc (sizeof (list*));
            a[x]=a[x]->next;
            a[x]->data=y;
            a[x]->next=NULL;
        }
        else
        {
            b[x]=(list*) malloc (sizeof (list*));
            b[x]->data=y;
            b[x]->next=NULL;
            a[x]=b[x];
        }
        if (b[y])
        {
            a[y]->next=(list*) malloc (sizeof (list*));
            a[y]=a[y]->next;
            a[y]->data=x;
            a[y]->next=NULL;
        }
        else
        {
            b[y]=(list*) malloc (sizeof (list*));
            b[y]->data=x;
            b[y]->next=NULL;
            a[y]=b[y];
        }
    }
    for (i=1; i<=n; i++) if (!b[i]) nr++;
    for (i=1; i<=n; i++)
        if (b[i])
        {
            nr++;
            parse (a,b,i);
        }
    fprintf (out,"%d\n",nr);
    return 0;
}

void parse (list *a[],list *b[],int i)
{
    if (a[i])
    {
        a[i]=NULL;
        while (b[i])
        {
            parse (a,b,b[i]->data);
            b[i]=b[i]->next;
        }
    }
}