Cod sursa(job #2382944)

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

FILE* fin;
FILE* fout;

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

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

	return root;
}

void Merge3(int* roots, int a, int b)
{
	a = Find3(roots, a);
	b = Find3(roots, b);

	if (roots[a] == roots[b])
	{
		roots[a]--;
		roots[b] = a;
	}
	else
	{
		if (roots[a] < roots[b])
			roots[b] = a;
		else
			roots[a] = b;
	}
}

int main(void)
{
	int n, m;
	int i;
	int finalResult = 0;

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

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

	int* roots = malloc(sizeof(int) * (n + 1));
	char* isRoot = malloc(sizeof(char) * (n + 1));

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

	memset(isRoot, 0, sizeof(char) * (n + 1));

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

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

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

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

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

	free(isRoot);
	isRoot = NULL;

	free(roots);
	roots = NULL;

	fclose(fin);
	fclose(fout);

	return 0;
}