苗火 Nicholas

[Data structures]Merge forest set

2019-8-5 萧 写技术

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

typedef struct _PTreeNode{
	int data;
	int parent;
}PTreeNode;

typedef struct _PTree{
	PTreeNode nodes[MAX];
	int n;
}PTree;

int find_mfset(PTree *S, int i)
{
	int j,k,t;
	if(i<1 || i>S->n){
		return -1;
	}
	for(j=i; S->nodes[j].parent > 0; j = S->nodes[j].parent);
	/* Get shortcut */
	for(k=i; k!=j; k=t){
		t = S->nodes[k].parent;
		S->nodes[k].parent = j;
	}
	return j;
}

/* j:root, i:leaf */
int merge_mfset(PTree *S, int i, int j)
{
	if(i<1 || i>S->n || j<1 || j>S->n){
		return -1;
	}	
	if(S->nodes[i].parent > S->nodes[j].parent){
		/* Node[j]'s members is more */ 
		S->nodes[j].parent += S->nodes[i].parent;
		S->nodes[i].parent = j;
	}else{
		/* Node[i]'s members is more */ 
		S->nodes[i].parent += S->nodes[j].parent;
		S->nodes[j].parent = i;
	}
	return 0;
}

void main()
{
	PTree S;	
	int data[] = {-1,1,2,3,4,5,6,7,8}; /* From 1 */
	int rule[][2] = {{1,2},{3,4},{5,6},{7,8},{1,3},{5,7},{1,5}};
	int n = sizeof(data)/sizeof(int)-1;
	int m = sizeof(rule)/sizeof(int)/2;
	int i,j;
	int a,b;

	printf("log.anycle.com\n\n");
	printf("Original data:\n");
	for(i=1; i<=n; i++){
		S.nodes[i].data = data[i];
		S.nodes[i].parent = -1;

		printf("   %2d(%2d)", S.nodes[i].data, S.nodes[i].parent);
	}	
	S.n = n;
	printf("\n");
	for(i=0; i<m; i++){
		printf(" (%2d, %2d)", rule[i][0], rule[i][1]);
	}
	printf("\n");

	

	printf("Merge:\n");
	for(i=0; i<m; i++){
		a = find_mfset(&S, rule[i][0]);
		b = find_mfset(&S, rule[i][1]);
		if(a != b){
			merge_mfset(&S, a, b);
			for(j=1; j<=n; j++){
				printf(" %2d(%2d)", S.nodes[j].data, S.nodes[j].parent);
			}
			printf("\n");
		}
	}
	printf("\n");


	printf("Find:\n");
	for(j=1; j<=n; j++){
		find_mfset(&S, j);
	}
	for(j=1; j<=n; j++){
		printf(" %d(%d)", S.nodes[j].data, S.nodes[j].parent);
	}
	printf("\n");


}

标签: Data Structures data_structures