Cod sursa(job #2794246)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 4 noiembrie 2021 15:47:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#define _CRT_SECURE_NO_WARNINGS
#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;
    fi=fopen("dfs.in","r");
    fo=fopen("dfs.out","w");

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

    for(int i=1; i<=m; i++)
    {
        int x,y;
        fscanf(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(fo,"%d",rez);

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