Cod sursa(job #2089062)

Utilizator adireusadireus adireus Data 16 decembrie 2017 10:40:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdlib.h>
#include <stdio.h>

struct node {
	int data;
	struct node *next;
};

int list_add_first(struct node **head, int val)
{
	struct node *tmp = malloc(sizeof(struct node));
	tmp->data = val;
	tmp->next = *head;
	*head = tmp;
	return 0;
}

void dfs(struct node **graph, int s, int* marked)
{
	if (graph[s] == NULL)
		return;

	for (struct node *p = graph[s]; p!= NULL; p = p->next){
		if(!marked[p->data]) {
			marked[p->data] = 1;
			dfs(graph, p->data, marked);
		}
	}
}

int main()
{
	FILE *infile, *outfile;
	struct node **graph;
	int n, m;
	int *marked;
	int count = 0;

	infile = fopen("dfs.in", "r");
	outfile = fopen("dfs.out", "w");

	fscanf(infile, "%d %d", &n, &m);
	marked = malloc ((n+1) * sizeof(int));
	graph = malloc((n+1) * sizeof(struct node*));
	for (int i = 0; i <= n ; i++) {
		graph[i] = NULL;
		marked[i] = 0;
	}

	for (int i = 0; i < m ;i++) {
		int x, y;
		fscanf(infile, "%d %d", &x, &y);
		list_add_first(&graph[x], y);
		list_add_first(&graph[y], x);
	}

	for (int i = 1; i <= n; i++) {
		if(marked[i] == 0) {
			count++;
			dfs(graph, i, marked);
		}
	}

	fprintf(outfile, "%d", count);
}