Cod sursa(job #803393)

Utilizator alexclpAlexandru Clapa alexclp Data 27 octombrie 2012 15:02:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
#include <stdlib.h>

#define N 200000
#define M 100001

typedef struct Muchie {
    int x;
    int y;
};

struct Muchie vm[N];
int g[M];
int n, m;
int *a[M];
int c[M];
int viz[N];

FILE *in;
FILE *out;

void citire()
{
    fscanf(in, "%d %d", &n, &m);
    int i;
    for (i = 0; i < m; i++) {
        fscanf(in, "%d %d", &vm[i].x, &vm[i].y);
        g[vm[i].x]++;
        g[vm[i].y]++;
    }
    for (i = 1; i <= n; i++) {
        a[i] = (int*)malloc(g[i]*sizeof(int));
    }
    for (i = 0; i < m; i++) {
        a[vm[i].x][++c[vm[i].x]] = vm[i].y;
        a[vm[i].y][++c[vm[i].y]] = vm[i].x;
    }
}

void fill(int x)
{
    viz[x] = 1;
    int i, y;

    for (i = 1; i <= g[x]; i++) {
        y = a[x][i];
        if (!viz[y]) {
            fill(y);
        }
    }
}

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

    citire();

    int i;
    int count = 0;

    for (i = 1; i <= n; i++) {
        if (!viz[i]) {
            count ++;
            fill(i);
        }
    }

    fprintf(out, "%d\n", count);
    return 0;
}