lset.h

ACM经典算法ACM经典算法ACM经典算法

/************************************************************************
First Created:2007-2-3  By Liuctic

Lset.h

void MakeSet(int n);     To initial
void Union(int x,int y); To union two elements(union by rank)
int FindSet(int x);      Find which set does x belong to(path compression)
int size();

Modified on: 2007-2-3
void compress_all()      compress all the path. In order to calculate number of group members
*************************************************************************/
#ifndef LSET_H
#define LSET_H
#include<cstdio>
class Lset
{
	int *p,*rank;
	int sz;
	void link(int x,int y)
	{
		if(x==y) return;
		if(rank[x]>rank[y]) p[y]=x;
		else p[x]=y;
		if(rank[x]==rank[y]) rank[y]++;
	}
public:
	void MakeSet(int n)
	{
		int i;
		delete[] p;delete[] rank;
		sz=n;
		p=new int[sz];rank= new int[sz];
		for(i=0;i<n;i++) {p[i]=i;rank[i]=0;}
	}
	Lset(int n)
	{
		int i;
		p=new int[n];rank=new int[n];
		sz=n;
		for(i=0;i<n;i++) {p[i]=i;rank[i]=0;}
	}
	~Lset(){delete[] p; delete[] rank;}
	void Union(int x,int y)
	{
		link(FindSet(x),FindSet(y));
	}
	int FindSet(int x)
	{
		if(x!=p[x]) p[x]=FindSet(p[x]);
		return p[x];
	}
	int size(){return sz;}
	void compress_all()
	{
	    int i;
        for(i=0;i<sz;i++) FindSet(i); 
	}
};
#endif