unionfind.cpp

这是研究生课程计算方法与技术中讲到的UnionFind算法的具体实现代码。

#include<iostream.h>

struct Dtree_node
{
	int ID;
	int Count;
	int Weight;
	int FatherID;
};
static int new_weight[5]={0};

Dtree_node tree[5]={{0,5,0,0},{1,4,1,0},{2,3,1,1},{3,2,1,2},{4,1,1,3}};

int Find(int i)
{
//	weight = 0;
	if(tree[i].FatherID != tree[i].ID)
	{
		tree[i].FatherID = Find (tree[i].FatherID);
		if(i<=1)
		{
			new_weight[i] = tree[i].Weight;
		}
		else
		{
			new_weight[i] = new_weight[i-1]+tree[i].Weight;		
		}
	}
	else
	{
		new_weight[i] =0;
	}
	return tree[i].FatherID;
}

int Find_Depth(int i)
{

	Find(i);
	 
	if(i==0)
	{
		return 0;
	}
	else
	{
		return new_weight[i];//tree[i].Weight+new_weight[i-1];
	}
}

void main()
{
	for(int i=0;i<5;i++)
	{
		cout<<"The current depth of"<<i<<"is"<<Find_Depth(i)<<endl;
	}
}