您所在位置：主题：[原创]并查集模板
Sedgewick
[专家分：0] 发布于 2008-03-11 20:33:00
最近经常遇到需要用Union-Find Data-Structure来解决的题目，于是根据资料实现了一个。发现蛮好用的，希望对你能有帮助。
# include <iostream>
# include <vector>
# include <cassert>
using namespace std;
class UnionFindSets
{
public:
// makeSet(x): create a set that contains the single element x.
[b]void makeSet(int l, int r);[/b]
// find(x): return the set that contains x.
[b]int find(int x);[/b]
// unite(A,B) - return the set which is the union of A and B. Namely A ∪ B. Namely,
// this operation merges the two sets A and B and return the merged set.
[b]void unite(int x, int y);[/b]
bool connected(int x, int y);
int differentSet(int l, int r);
private:
vector<int> parent;
vector<int> rank;
};
void UnionFindSets::makeSet(int l, int r)
{
// The initial partition has each element in a set by itself.
assert(1 <= l && l <= r);
[b]parent.resize(r + 1);[/b]
[b]rank.resize(r + 1);[/b]
for (int x = l; x <= r; ++x) {
parent[x] = x;
rank[x] = 0;
}
}
int UnionFindSets::find(int x)
{
if (x != parent[x]) {
// Since, anyway, we travel the path to the root during a find operation,
// we might as well hung all the nodes on the path directly on the root.
[b]parent[x] = find(parent[x]);[/b]
}
return parent[x];
}
void UnionFindSets::unite(int x, int y)
{
int a = find(x);
int b = find(y);
if (rank[a] > rank[b]) {
// Always hang the smaller tree on the larger tree.
parent[b] = a;
} else if (rank[a] < rank[b]) {
parent[a] = b;
} else {
parent[a > b ? a : b] = a < b ? a : b;
++rank[a > b ? a : b];
}
}
bool UnionFindSets::connected(int x, int y)
{
return find(x) == find(y);
}
int UnionFindSets::differentSet(int l, int r)
{
int count = 0;
for (int x = l; x <= r; ++x) {
if (parent[x] == x) {
++count;
}
}
return count;
}
[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]
# include <iostream>
# include <vector>
# include <cassert>
using namespace std;
class UnionFindSets
{
public:
// makeSet(x): create a set that contains the single element x.
[b]void makeSet(int l, int r);[/b]
// find(x): return the set that contains x.
[b]int find(int x);[/b]
// unite(A,B) - return the set which is the union of A and B. Namely A ∪ B. Namely,
// this operation merges the two sets A and B and return the merged set.
[b]void unite(int x, int y);[/b]
bool connected(int x, int y);
int differentSet(int l, int r);
private:
vector<int> parent;
vector<int> rank;
};
void UnionFindSets::makeSet(int l, int r)
{
// The initial partition has each element in a set by itself.
assert(1 <= l && l <= r);
[b]parent.resize(r + 1);[/b]
[b]rank.resize(r + 1);[/b]
for (int x = l; x <= r; ++x) {
parent[x] = x;
rank[x] = 0;
}
}
int UnionFindSets::find(int x)
{
if (x != parent[x]) {
// Since, anyway, we travel the path to the root during a find operation,
// we might as well hung all the nodes on the path directly on the root.
[b]parent[x] = find(parent[x]);[/b]
}
return parent[x];
}
void UnionFindSets::unite(int x, int y)
{
int a = find(x);
int b = find(y);
if (rank[a] > rank[b]) {
// Always hang the smaller tree on the larger tree.
parent[b] = a;
} else if (rank[a] < rank[b]) {
parent[a] = b;
} else {
parent[a > b ? a : b] = a < b ? a : b;
++rank[a > b ? a : b];
}
}
bool UnionFindSets::connected(int x, int y)
{
return find(x) == find(y);
}
int UnionFindSets::differentSet(int l, int r)
{
int count = 0;
for (int x = l; x <= r; ++x) {
if (parent[x] == x) {
++count;
}
}
return count;
}
[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]
