Cod sursa(job #2594964)

Utilizator razvan.ursatanuUrsatanu Razvan razvan.ursatanu Data 6 aprilie 2020 20:29:47
Problema Parcurgere DFS - componente conexe Scor 10
Compilator c-64 Status done
Runda laborator_7_sd_313cab Marime 2.03 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    void *data;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    int size;
} LinkedList;

typedef struct {
    LinkedList **neighbors;
    int nodes;
} ListGraph;

void init_list_graph(ListGraph *graph, int nodes) {
    graph->nodes = nodes;
    graph->neighbors = malloc(nodes * sizeof(LinkedList*));
    for(int i = 1; i <= nodes; ++i) {
        graph->neighbors[i] = malloc(sizeof(LinkedList));
        graph->neighbors[i]->head = NULL;
        graph->neighbors[i]->tail = NULL;
        graph->neighbors[i]->size = 0;
    }
}

void add_edge_list_graph(ListGraph *graph, int src, int *dest) {
    Node *nod;
    nod = malloc(sizeof(Node));
    nod->data = dest;
    nod->next = NULL;
    Node *p;
    p = graph->neighbors[src]->head;
    if(p == NULL) {
        graph->neighbors[src]->head = nod;
        graph->neighbors[src]->tail = nod;
        graph->neighbors[src]->size++;
        return;
    }
    while(p->next != NULL) {
        p = p->next;
    } 
    p->next = nod;
    graph->neighbors[src]->tail = nod;
    graph->neighbors[src]->size++;
}

void dfs_list_graph(ListGraph *lg, int node, int *visited) {
    Node *p;
    p = lg->neighbors[node]->head;
    visited[node] = 1;
    while(p != NULL) {
        if(visited[*(int*)p->data] == -1){
             dfs_list_graph(lg, *(int*)p->data, visited);
        }
        p = p->next;
    }
}

int main() {
	int n, m, x[101], y[101], visited[101];
	ListGraph *lg;
	lg = malloc(sizeof(ListGraph));
	FILE *in = fopen("dfs.in", "rt");
	FILE *out = fopen("dfs.out", "wt");
	fscanf(in, "%d%d", &n, &m);
	for(int i = 1; i <= m; ++i){
		fscanf(in, "%d%d", &x[i], &y[i]);
	}
	init_list_graph(lg, n);
	for(int i = 1; i <= m; ++i){
		add_edge_list_graph(lg, x[i], &y[i]);
		add_edge_list_graph(lg, y[i], &x[i]);
	}
	for(int i = 1; i <= n; ++i){
		visited[i] = -1;
	}
	int count = 0;
	for(int i = 1; i <= n; ++i){
		if(visited[i] == -1){
			dfs_list_graph(lg, i, visited);
			count++;
		}
	}
	fprintf(out, "%d", count);
	return 0;
}