Cod sursa(job #2225230)

Utilizator AraldaAralda Pacurar Aralda Data 26 iulie 2018 14:06:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.33 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct node {

	int key;
	struct node* next;

}node;

node* adj[100001];
int descoperit[100001];

void enqueue(node** first, int key) {

	node* p = (node *)malloc(sizeof(node));
	if (p == NULL) {

		perror("malloc failed");
	}

	p->key = key;
	p->next = NULL;

	if (*first == NULL) {

		*first = p;
	}
	else{

		node* q = *first;

		while (q->next != NULL) {

			q = q->next;
		}

		q->next = p;
	}
}

void DFS(int s) {

	descoperit[s] = 1;

	node* p = adj[s];
	while (p) {

		if (descoperit[p->key] == 0) {

			DFS(p->key);
		}

		p = p->next;
	}
}

int main() {

	FILE* ip;
	FILE* op;

	ip = fopen("dfs.in", "r");
	if (ip == NULL) {

		perror("Error opening input file");
		return 1;
	}

	op = fopen("dfs.out", "w");
	if (op == NULL) {

		perror("Error opening output file");
		return 1;
	}

	int n, m;

	fscanf(ip, "%d%d", &n, &m);

	for (int i = 0; i < m; i++) {

		int x, y;

		fscanf(ip, "%d%d", &x, &y);

		enqueue(&adj[x], y);
		enqueue(&adj[y], x);
	}

	int componente_conexe = 0;

	for (int i = 1; i <= n; i++) {

		if (descoperit[i] == 0) {

			DFS(i);
			componente_conexe++;
		}
	}

	fprintf(op, "%d", componente_conexe);

	fclose(ip);
	fclose(op);

	return 0;
}