package DataStructures.Set;

// DisjSets class

//

// CONSTRUCTION: with int representing initial number of sets

//

// ******************PUBLIC OPERATIONS*********************

// void union( root1, root2 ) --> Merge two sets

// int find( x ) --> Return set containing x

// ******************ERRORS********************************

// No error checking is performed

/**

* Disjoint set class. (Package friendly so not used accidentally) Does not use

* union heuristics or path compression. Elements in the set are numbered

* starting at 0.

*

* @author Mark Allen Weiss

* @see DisjSetsFast

*/

class DisjSets {

/**

* 构造函数

*

* @param numElements

* 初始集合的个数

*/

public DisjSets(int numElements) {

s = new int[numElements];

for (int i = 0; i < s.length; i++)

s[i] = -1; //初始化为-1

}

/**

* 合并操作

*

* @param root1

* the root of set 1.

* @param root2

* the root of set 2.

*/

public void union(int root1, int root2) {

s[root2] = root1;

}

/**

* 查找操作

*

* @param x

* 要查找的元素

* @return 包含x的集合

*/

public int find(int x) {

if (s[x] < 0)

return x;

else

return find(s[x]);

}

private int[] s;

// Test main; all finds on same output line should be identical

public static void main(String[] args) {

int numElements = 128;

int numInSameSet = 16;

DisjSets ds = new DisjSets(numElements);

int set1, set2;

for (int k = 1; k < numInSameSet; k *= 2) {

for (int j = 0; j + k < numElements; j += 2 * k) {

set1 = ds.find(j);

set2 = ds.find(j + k);

ds.union(set1, set2);

}

}

for (int i = 0; i < numElements; i++) {

System.out.print(ds.find(i) + "*");

if (i % numInSameSet == numInSameSet - 1)

System.out.println();

}

System.out.println();

}

}