Disjoint Sets
Two Heuristics:
- Union-by-Rank
- Path Compression
Funstion | Time |
---|---|
CREATE-SET(x) | O(1) |
UNION(x,y) | O(1) |
FIND-SET(x) | O(m*a(m,n)) |
#include <iostream> using namespace std; int r[100]; int p[100]; void CREATE_SET(int x) { p[x] = x; r[x] = 0; } void UNION(int x, int y) { /* Union-by-rank heuristic */ if(r[x] < r[y]) p[x] = y; else if ( r[x] > r[y]) p[y] = x; else { p[x] = y; r[y] ++; } } int FIND_SET(int x) { int z = x; int z1; while(p[x] != x) x = p[x]; /* Path Compression heuristic */ while(p[z] != z) { z1 = z; z = p[z]; p[z1] = x; } return x; }
page revision: 0, last edited: 07 Dec 2006 17:54