Cod sursa(job #2382701)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 18 martie 2019 16:48:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <stdio.h>

#define TRUE  1
#define FALSE 0

typedef char byte;

int Find3(int* roots, int node)
{
	int root = node;
	while (roots[root] != root)
	{
		root = roots[root];
	}

	while (roots[node] != root)
	{
		int tmp = node;
		node = roots[node];
		roots[tmp] = root;
	}

	return root;
}

void Merge4(int* roots, int* childrenCount, int a, int b)
{
	int rootA = Find3(roots, a);
	int rootB = Find3(roots, b);

	if (childrenCount[rootA] < childrenCount[rootB])
	{
		roots[rootA] = rootB;
		childrenCount[rootB]++;
		childrenCount[rootB] += childrenCount[rootA];
	}
	else
	{
		roots[rootB] = rootA;
		childrenCount[rootA]++;
		childrenCount[rootA] += childrenCount[rootB];
	}
}

int main(void)
{
	FILE* fin;
	FILE* fout;

	int n, m;
	int i;
	int finalResult = 0;
	int arrayLength;

	fin = fopen("dfs.in", "r");
	fout = fopen("dfs.out", "w");

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

	arrayLength = n + 1;

	int* roots = malloc(sizeof(int) * arrayLength);
	int* childrenCount = malloc(sizeof(int) * arrayLength);
	byte* isRoot = malloc(sizeof(byte) * arrayLength);

	for (i = 1; i <= n; i++)
	{
		roots[i] = i;
	}

	memset(childrenCount, 0, sizeof(int) * arrayLength);
	memset(isRoot, FALSE, sizeof(byte) * arrayLength);

	for (int i = 0; i < m; i++)
	{
		int node1, node2;
		fscanf(fin, "%d %d", &node1, &node2);

		if (Find3(roots, node1) != Find3(roots, node2))
		{
			Merge4(roots, childrenCount, node1, node2);
		}
	}

	for (int i = 1; i <= n; i++)
	{
		isRoot[Find3(roots, i)] = TRUE;
	}

	for (int i = 1; i <= n; i++)
	{
		if (isRoot[i])
			finalResult++;
	}

	fprintf(fout, "%d", finalResult);

	free(isRoot);
	isRoot = NULL;

	free(childrenCount);
	childrenCount = NULL;

	free(roots);
	roots = NULL;

	fclose(fin);
	fclose(fout);

	return 0;
}