Cod sursa(job #803392)

Utilizator crazzytudTudor Popa crazzytud Data 27 octombrie 2012 15:01:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100001
FILE *in;
FILE *out;



typedef struct list{
    int info;
    struct list *next;
};

struct list *v[N];
int viz[N];
int n,m;

void adauga(int x, int y)
{
    struct list *nou = (struct list*) malloc(sizeof(struct list));

    nou -> info = y;
    nou -> next = v[x];
    v[x] = nou;
}

void citire()
{
    fscanf(in,"%d%d",&n,&m);
    int x,y,i;
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        adauga(x,y);
        adauga(y,x);
    }
}

void dfs(int x)
{
    struct list *p;
    viz[x]=1;
    for(p=v[x]; p!=NULL; p = p -> next)
        if(!viz[ p->info ])
            dfs(p -> info);
}


int main()
{
    in = fopen("dfs.in","r");
    out = fopen("dfs.out","w");

    citire();
    int i,count=0;
    for(i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            count++;
            dfs(i);
        }
    }
    fprintf(out,"%d",count);

    return 0;
}