Cod sursa(job #763907)

Utilizator igsifvevc avb igsi Data 3 iulie 2012 14:59:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <stdlib.h>

struct graph
{
    int edge;
    struct graph *next;
} *G[100001];

int n, nrComponents; 
char used[100001];

void df(int vertex)
{
    struct graph *p;
    used[vertex] = 1;

    for(p = G[vertex]; p ; p = p->next)
        if( used[p->edge] == 0)
            df(p->edge);
}

int main()
{
    FILE *in = fopen("dfs.in", "r");
    FILE *out = fopen("dfs.out", "w");
    struct graph *p;
    int m, a, b;

    for(fscanf(in, "%d %d", &n, &m); m; m--)
    {
    	fscanf(in, "%d %d", &a, &b);
        p = malloc(sizeof(struct graph));
        p->edge = b;
        p->next = G[a];
        G[a] = p;
        p = malloc(sizeof(struct graph));
        p->edge = a;
        p->next = G[b];
        G[b] = p;
    }
    
    for(; n; n--)
        if(used[n] == 0)
            nrComponents++,
            df(n);
            
    fprintf(out, "%d\n", nrComponents);

    fclose(in), fclose(out);
    return 0;
}