博文
并查集的应用PKU1703(2008-08-21 13:13:00)
摘要：/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:满天飞
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////
#include<stdio.h>
#define MAX 100010
int ary[MAX];
int opt[MAX];
void Init(int n)
{
int i;
for(i = 0; i <= n+10; ++i)
{
ary[i] = -1;
opt[i] = -1;
}
}
int Find(int index)
{
if(ary[index] < 0)
return index;
return ary[index] = Find(ary[index]);
}
int Union(int first, int second)
{
int i, j;
if(second == -1)
return first;
i = Find(first);
j = Find(second);
并查集的应用PKU2524(2008-08-21 13:12:00)
摘要：/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:满天飞
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////
#include<iostream>
using namespace std;
class Set
{
private:
int* ary;
int length;
public:
int Find(int index);
bool Union(int first, int second);
Set(int n);
int Count();
virtual ~Set(){delete[]ary;}
};
int Set::Count()
{
int i, ct;
ct = 0;
for(i = 1; i <= length; ++i)
{
if(ary[i] < 0)
......
并查集的应用PKU2492(2008-08-21 13:11:00)
摘要：/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:梁岳传
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////
#include<iostream>
using namespace std;
#define MAX 1000010
int ary[MAX];
int opt[MAX];
void Init(int n)
{
int i;
for(i = 0; i <= n+10; ++i)
{
ary[i] = -1;
opt[i] = -1;
}
}
int Find(int index)
{
if(ary[index] < 0)
return index;
return ary[index] = Find(ary[index]);
}
int Union(int first, int second)
{
int i, j;
if(second == -1)
return first;
i = Find(first);
j ......
并查集的应用PKU2236(2008-08-21 13:10:00)
摘要：/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:梁岳传
//作品时间:2008-8-16
//最后修改:2008-8-16
//Q Q 号码:280282813
//版权所有,翻版必究
////////////////////////////////////////
#include<iostream>
#include<cmath>
using namespace std;
typedef struct
{
int x;
int y;
int parent;
}Node;
class Set
{
public:
Node* ary;
int length;
public:
int Find(int index);
bool Union(int first, int second);
Set(int n);
virtual ~Set(){delete[]ary;}
};
Set::Set(int n)
{
int i;
ary = new Node[n+10];
length = n;
......
并查集的实现及应用:最小生成树(2008-08-15 10:40:00)
摘要：/////////////////////////////////////////
//作品名称:并查集的实现及应用
//作者姓名:梁岳传
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////
#include<iostream>
using namespace std;
class Set
{
private:
int* ary;
int length;
public:
int Find(int index);
bool Union(int first, int second);
Set(int n);
virtual ~Set(){delete[]ary;}
};
Set::Set(int n)
{
int i;
ary = new int[n];
length = n;
for(i = 0; i < n; ++i)
ary[i] = -1;
}
//将每次查找过的路线上的结点全部都指向根结点
int Set::Find(int index)
{
int i, j, t;
if(index < 0 || index >= length) return -1;
//查找index元素的根结点
for(i = index; ary[i] >= 0; i = ary[i]);
//将这条路线上的所有元素全部指向根结点
for(j = index; j != i; j = t){
t = ary[j];
ary[j] = i;
}
return i;