Cod sursa(job #2302626)

Utilizator flibiaVisanu Cristian flibia Data 14 decembrie 2018 21:56:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>

struct nod {
	int val;
	struct nod *next;
};

void baga(struct nod **q, int val) {
	if (q == NULL) {
		(*q) = malloc(sizeof(struct nod));
		(*q) -> next = NULL;
		(*q) -> val = val;
		return;
	}
	struct nod *p = malloc(sizeof(struct nod));
	p -> next = *q;
	p -> val = val;
	*q = p;
}

void dfs(int p, int *viz, struct nod **q) {
	viz[p] = 1;
	for (struct nod *v = q[p]; v != NULL; v = v -> next)
		if (!viz[v -> val])
			dfs(v -> val, viz, q);
}

int main() {
	FILE *in = fopen("dfs.in", "r");
	FILE *out = fopen("dfs.out", "w");
	int n, m;
	fscanf(in, "%d %d", &n, &m);
	int *viz = calloc(n, sizeof(int));
	struct nod **q = calloc(n, sizeof(struct nod *));
	for (int i = 0; i < m; i++) {
		int x, y;
		fscanf(in, "%d %d", &x, &y);
		baga(&q[x - 1], y - 1);
		baga(&q[y - 1], x - 1);
	}
	int nr = 0;
	for (int i = 0; i < n; i++)
		if (viz[i] == 0) {
			dfs(i, viz, q);
			nr++;
		}
	fprintf(out, "%d", nr);
	return 0;
}