ufset.h

完全由C语言实现的图的相关操作

#ifndef UFSET_H
#define UFSET_H
/*
并查集 (Union-Find Sets) 是一种简单而用途广泛的高级数据结构。
并查集可以描述这样一个逻辑结构：有若干个元素，将其分成若干个不相交的集合，每个集合相互独立。使用并查集可以方便地进行以下两种操作：
1、 判断两个元素是否属于同一个集合。
2、 合并两个元素所在的集合。

并查集机构的储存结构为一棵采用双亲表示法的树，通常用数组来储存。一般应用中每个元素还有一个权值：
*/
typedef struct UFSet
{
     int parent;
     int rank;
}UFSet;

//其中father为正数时表示该节点的父节点下标，为负数时表示该节点为一个根节点，其绝对值为该集合包含的节点总数。
//rank表示权值，在不同问题中有不同的含义。
//对于并查集，主要有以下四种操作
Status InitUFSet(UFSet* set,int n);
//初始化并查集
int UFSetFind(UFSet* set,int x);
//初始条件：存在并查集set，和要查找的元素x，x一定在某个集合中
//操作结果：返回该元素所属于的集合
int Union(UFSet* set,int a,int b);
//初始条件：存在并查集set,集合a,集合b
//操作结果：合并集合a，b
 
#endif