Cod sursa(job #2746307)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 27 aprilie 2021 17:58:53
Problema Parcurgere DFS - componente conexe Scor 5
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.26 kb
    ///#539 in pbinfo
    ///the graph is UNoriented
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> ///pentru a putea folosi boool

FILE *f,*g;

bool viz[100001];
typedef struct sll
{
    int value;
    struct sll *next;
}sll;
sll* v[100001];

void dfs(int start, int n, sll* v[])
{
    viz[start]=1;
    int i;
    sll* ve=v[start];
    while(ve != NULL)
    {
        if(!viz[ve->value])
            dfs(ve->value,n,v);
        ve=ve->next;
    }
}

sll* create( int n2)
{
    sll* p;
    p=(sll* )calloc(1,sizeof(sll));
    if(p)
    {
        p->value=n2;
        p->next=NULL;
    }
    else
    {
        printf("Nu s-a putut aloca memoria!");
        exit(2);
    }
}

void insert(sll* v[], int n1, int n2)
{
    sll* p;
    p=create(n2);
    if(v[n1] == NULL)///nu am niciun element
        v[n1]=p;
    else///am cel putin un element
    {///trebuie inserati vecinii in ordine crescatoare
        if(v[n1]->value > n2)
        {
            p->next=v[n1];
            v[n1]=p;///se va modifica v[n1]
        }
        else
        {
            sll* p1=v[n1];
            sll* p2=v[n1]->next;
            while(p2 != NULL)
            {
                if(p1->value <= n2 && n2 <= p2->value)
                {
                    p->next=p2;
                    p1->next=p;
                    break;
                }
                p1=p2;
                p2=p2->next;
            }
            if(p2==NULL)///se va insera la final
                p1->next=p;
        }
    }
}
int main()
{
    f=fopen("dfs.in","r");
    if(!f)
    {
        printf("The input file can not be opend!");
        exit(1);
    }
    g=fopen("dfs.out","w");
    if(!g)
    {
        printf("The output file can not be opened!");
        exit(1);
    }
    int n,m,x,n1,n2;
    ///int matric[100][100]={0};
    fscanf(f,"%d %d",&n,&m);
    int i;
    for(i=1;i<=n;++i) v[i]=NULL;///!!!
    for(i=1;i<=m;++i)
    {
        fscanf(f,"%d %d",&n1,&n2);
        insert(v,n1,n2);
        insert(v,n2,n1);
    }
    int nr=0;
    for(i=1;i<=n;++i)
        if(!viz[i])
        {
            ++nr;
            dfs(i,n,v);
        }
    fprintf(g,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}