Cod sursa(job #2794245)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 4 noiembrie 2021 15:45:49
Problema Parcurgere DFS - componente conexe Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct linked_list_node
{
    struct linked_list_node *next;
    int value;
} linked_list_node;

linked_list_node *Last_element[100005];

void add_element_to_linked_list(int which, int value)
{
    linked_list_node *node=(linked_list_node *)malloc(sizeof(linked_list_node));
    node->value=value;
    node->next=Last_element[which];

    Last_element[which]=node;
}

void add_edge(int x, int y)
{
    add_element_to_linked_list(x,y);
    add_element_to_linked_list(y,x);
}

int Viz[100005];

void dfs(int node)
{
    Viz[node]=1;
    for(linked_list_node *linked_list_element=Last_element[node]; linked_list_element!=NULL; linked_list_element=(linked_list_element->next))
    {
        int neighbour=linked_list_element->value;

        if(!Viz[neighbour])
            dfs(neighbour);
    }
}

int main()
{
    FILE *fi,*fo;
    fopen_s(&fi,"dfs.in","r");
    fopen_s(&fo,"dfs.out","w");

    int n,m;
    fscanf_s(fi,"%d%d",&n,&m);

    for(int i=1; i<=m; i++)
    {
        int x,y;
        fscanf_s(fi,"%d%d",&x,&y);

        add_edge(x,y);

    }
   
    int rez=0;
    for(int i=1; i<=n; i++)
    {
        if(!Viz[i])
        {
            rez++;
            dfs(i);
        }
    }

    fprintf_s(fo,"%d",rez);

    fclose(fi);
    fclose(fo);
    return 0;
}