Cod sursa(job #1659135)

Utilizator experiment322Alexandru-Damian Manea experiment322 Data 22 martie 2016 00:03:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>

enum {
	NMAX = 100001
};

typedef struct node {
	int val;
	struct node *next;
} node_t;

static node_t *GRAPH[NMAX];
static int N, M, COUNT, VISITED[NMAX];

static void Add(int a, int b)
{
	node_t *t;
	t = malloc(sizeof(node_t));
	t->val = b;
	t->next = GRAPH[a];
	GRAPH[a] = t;
}

static void Read(void)
{
	int i, a, b;
	scanf("%i%i", &N, &M);
	for (i = 1; i <= M; ++i) {
		scanf("%i%i", &a, &b);
		Add(a, b);
		Add(b, a);
	}
}

static void Mark(int v)
{
	node_t *t;
	VISITED[v] = 1;
	t = GRAPH[v];
	while (t != NULL) {
		if (!VISITED[t->val]) {
			Mark(t->val);
		}
		t = t->next;
	}
}

static void Clean(node_t *t)
{
	if (t->next != NULL) {
		Clean(t->next);
		free(t);
	}
}

int main(void)
{
	int i;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	Read();
	for (i = 1; i <= N; ++i) {
		if (!VISITED[i]) {
			++COUNT;
			Mark(i);
		}
	}
	for (i = 1; i <= N; ++i) {
		if (GRAPH[i] != NULL) {
			Clean(GRAPH[i]);
		}
	}
	printf("%i\n", COUNT);
	return 0;
}