并查集类 - 小阮的菜田

随笔-141 评论-9 文章-3 trackbacks-0

并查集提供的操作：
1. 合并两个集合。
2. 判断两个元素是否在同一个集合里边。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

using namespace std;

const int MAXN=1001;

class UFS{

public:

int F[MAXN];

tUFS(){

for (int i=1;i<MAXN;i++)F[i]=-i;

}

int findroot(int a){

int r=a,t;

while (F[r]>0) r=F[r];

while (F[a]>0) {t=F[a];F[a]=r;a=t;}

return r;

}

void Union(int a,int b){

F[findroot(a)]=findroot(b);

}

bool Judge(int a,int b){

return F[findroot(a)]==F[findroot(b)];

}

int getroot(int a){

return -F[findroot(a)];

}

};

posted on 2011-05-03 20:27 小阮阅读(277) 评论(0) 编辑收藏引用所属分类: 数据结构和算法

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: [网络流]骑士共存问题 [网络流] 餐巾计划问题 ural 1297 最长回文子串(后缀数组) SPOJ 694 Distinct Substrings(不同子串个数, 后缀数组) 并查集类次短路径与次小生成树问题的简单解法高精计算 pku 1204 Word Puzzles (trie) pku 1200 Crazy Search (Rabin Karp) [网络流] 方格取数问题 ( 二分图点权最大独立集, 最小割模型, 最大流)

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

随笔分类