Cod sursa(job #1523384)

Utilizator andreeacozma95Cozma Andreea andreeacozma95 Data 12 noiembrie 2015 18:12:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <stdlib.h>

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

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

void add(int x,int y)
{
    NOD *p=malloc(sizeof(NOD));
    p->nr=y;
    p->urm=graf[x];
    graf[x]=p;
}

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

int main()
{
    int i,x,y;
    FILE *f=fopen("dfs.in","r");
    FILE *g=fopen("dfs.out","w");

    fscanf(f,"%d%d",&n,&m);
    for (i=0;i<m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    for (i=1;i<=n;i++)
        if (marc[i]==0)
        {
            marc[i]=1;
            nr_comp++;
            dfs(i);
        }

    fprintf(g,"%d\n",nr_comp);
    fclose(f);
    fclose(g);
    return 0;
}