#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");





}