알고리즘 도론 제21장 21-2 깊이 확정

1365 단어 알고리즘 도론

제목


 

코드

/* 
UnionFindSet.h 
   ,     ,     ,   0  
*/ 
#include    
using namespace std;  
  
#define MAXN 30005  
  
class UFS
{
public:
	int n;
	int p[MAXN+1];//     
	int rank[MAXN+1];  //       
	int depth[MAXN+1];
public:
	UFS(int size = MAXN);
	void clear();
	int Find_Set(int x);
	//a  b ,     
	void Union(int x, int y);
	void Make_Set(int x);
	void Link(int x, int y);
	void Graft(int r, int v);
};
UFS::UFS(int size):n(size)
{
	//   0  
	for(int i = 0; i <= n; i++)  
		Make_Set(i);  
}
void UFS::Make_Set(int x)
{
	p[x] = x;
	rank[x] = 0;
	depth[x] = 0;
}
void UFS::clear()
{
	for(int i = 0; i <= n; i++)  
		Make_Set(i);
}
int UFS::Find_Set(int x)
{
    int temp = x,sum = 0,ans;    
    while(temp != p[temp]) {    
       sum = sum + depth[temp];    
       temp = p[temp];    
    }    
    ans = temp;    
    while(x != ans) {    
       sum -= depth[x];    
       depth[x] += sum;    
       temp = p[x];    
       p[x] = ans;    
       x = temp;    
    }    
    return ans;
}
void UFS::Union(int x, int y)
{
	if(x == y)
		return ;
	Link(x, y);
}
void UFS::Link(int x, int y)
{
	p[x] = y;
	depth[x] = 1;
	rank[y] += rank[x];
}
void UFS::Graft(int r, int v)
{
	int x = Find_Set(r);
	int y = Find_Set(v);
	if(x < y)
		Union(x, y);
	else
		Union(y, x);
}

좋은 웹페이지 즐겨찾기