等价类_UFSet

直接上标题

//用于Kruskal 构造最小生成树的等价类

#include<iostream>
using namespace std;
class UFSet
{
protected:
	int n;		//等价类中元素的个数
	int * root; //root[i]表示i所在等价类的代表元素编号
	int * next;  //next[i]表示在等价类中，i的后面元素编号
	int * length;//lenght[i]表示i所在的等价类元素个数

public:
	UFSet(int size):n(size){
		root = next = length = 0;
		init();
		for(int i = 0;i<n;i++){
			root[i] = next[i] = i;
			length[i] = 1;
		}	
	}

	void init(){
		if(root == 0)root = new int[n];
		if(next == 0)next = new int[n];
		if(length == 0)length = new int[n];
	}
	~UFSet(void){
		if(root)delete []root;
		if(next)delete []next;
		if(length)delete []length;

	}

	void Union(int v,int u){
		if(root[v] == root[u])
			return;
		else if(length[root[v]]<=length[root[u]]){
		//v所在的等价类小于u所在的等价类 需要合并到u所在的等价类
			int rt = root[v];
			length[root[u]]+=length[rt];
			root[rt] = root[u];
			for(int j=next[rt];j!=rt;j = next[j])
				root[j] = root[u];
			//设置v等价类所有成员为u_root

			//交换rt_next 和root[u]_next
			int temp = next[rt];
			next[rt] = next[root[u]];
			next[root[u]] = temp;

		}else{
		//u所在的等价类小于v所在的等价类
			int rt = root[u];
			length[root[v]]+=length[rt];
			root[rt] = root[v];
			for(int j=next[rt];j!=rt;j = next[j])
				root[j] = root[v];
			int temp = next[rt];
			next[rt] = next[root[v]];
			next[root[v]] = temp;
		}
	}

	void show(){
		for(int i =0;i<n;i++){
			cout<<root[i] <<\" \";
		}cout<<endl;
		for(int i =0;i<n;i++){
			cout<<next[i] <<\" \";
		}cout<<endl;
		for(int i =0;i<n;i++){
			cout<<length[i] <<\" \";
		}cout<<endl;		
	}
};