Pagini recente » Cod sursa (job #2231657) | Cod sursa (job #2720870) | Cod sursa (job #2325119) | Monitorul de evaluare | Cod sursa (job #2382693)
#include <stdio.h>
FILE* fin;
FILE* fout;
int* childrenCount;
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 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)
{
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));
childrenCount = malloc(sizeof(int) * (n + 1));
char* isRoot = malloc(sizeof(char) * (n + 1));
for (i = 1; i <= n; i++)
{
roots[i] = i;
}
memset(childrenCount, 0, sizeof(int) * (n + 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))
{
Merge4(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(childrenCount);
childrenCount = NULL;
free(roots);
roots = NULL;
fclose(fin);
fclose(fout);
return 0;
}