Cod sursa(job #1522380)

Utilizator daianatoaderDaiana Toader daianatoader Data 11 noiembrie 2015 17:16:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct nod
{
    int v;
    struct nod *urm;
}NOD;

NOD *graf[100001];
char* marc;
int n,m,nrComp;

void add(int index,int varf)
{
    NOD *p=(NOD*)malloc(sizeof(NOD));
    p->v=varf;
    p->urm=graf[index];
    graf[index]=p;
}

void citire()
{
    int i,a,b;
    FILE *f=fopen("dfs.in","r");
    fscanf(f,"%d%d",&n,&m);
    marc=(char*)malloc((n+1)*sizeof(char));
    for(i=1; i<=n; i++)
        graf[i]=NULL, marc[i]=0;
    for(i=0; i<m; i++)
    {
        fscanf(f,"%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    fclose(f);
}

void dfs(int v)
{
    NOD *p;
    for(p=graf[v]; p!=NULL; p=p->urm)
        if(marc[p->v]==0)
        {
            marc[p->v]=1;
            dfs(p->v);
        }
}

void rezolvare()
{
    int i,ok;
    for(i=1; i<=n; i++)
        if(marc[i]==0)
        {
            marc[i]=1;
            nrComp++;
            dfs(i);
        }
}

void afisare()
{
    FILE *g=fopen("dfs.out","w");
    fprintf(g,"%d\n",nrComp);
    fclose(g);
}
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}