Cod sursa(job #2041169)

Utilizator tudormaximTudor Maxim tudormaxim Data 16 octombrie 2017 21:57:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.44 kb
// DFS.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define maxn 100005

typedef struct list {
	int node;
	struct list * next;
} graph;

void add_edge(graph ** head, int val) {
	if ((*head) == NULL) {
		(*head) = (graph*)malloc(sizeof(graph));
		(*head)->node = val;
		(*head)->next = NULL;
	} else {
		graph * new_node = (graph*)malloc(sizeof(graph));
		new_node->node = val;
		new_node->next = (*head);
		*(head) = new_node;
	}
}

void Dfs(graph *G[maxn], int node, int Vis[maxn]) {
	graph *it;
	Vis[node] = 1;
	for (it = G[node]; it != NULL; it = it->next) {
		if (Vis[it->node] == 0) {
			Dfs(G, it->node, Vis);
		}
	}
}

void print_list(graph *head, FILE *fout) {
	graph *it;
	for (it = head; it != NULL; it = it->next) {
		fprintf(fout, "%d ", it->node);
	}
	fprintf(fout, "\n");
}

int main() {
	FILE *fin = fopen("dfs.in", "r");
	FILE *fout = fopen("dfs.out", "w");
	graph * G[maxn];
	int i, x, y, n, m, cnt = 0, Vis[maxn];
	fscanf(fin, "%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		G[i] = NULL;
	}
	for (i = 0; i < m; i++) {
		fscanf(fin, "%d %d", &x, &y);
		add_edge(&G[x], y);
		add_edge(&G[y], x);
	}
	memset(Vis, 0, sizeof(Vis));
	for (i = 1; i <= n; i++) {
		if (Vis[i] == 0) {
			Dfs(G, i, Vis);
			cnt++;
		}
	}
	fprintf(fout, "%d \n", cnt);
	fclose(fin);
	fclose(fout);
    return 0;
}