Cod sursa(job #803360)

Utilizator crazzytudTudor Popa crazzytud Data 27 octombrie 2012 14:22:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<stdlib.h>
#define N 200000
#define M 100001

FILE *in;
FILE *out;

struct muchie{
    int x,y;
};
int n,m;

struct muchie vm[N];
int *a[M];
int c[M];
int g[M];
int viz[M];

void citire()
{
    int i;

    fscanf(in,"%d%d",&n,&m);

    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 dfs(int x)
{
    viz[x]=1;
    int i,y;

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

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

    return 0;
}