1. Dynamic connectivity
Enter several pairs of integers, among which a pair of integers p, q can be interpreted as “p and Q are connected”. P and Q are equals, so they have the following properties:
- Reflexivity: P and Q are connected;
- Symmetry: if P and Q are connected, then Q and P are also connected;
- Transitivity: If P and Q are connected and Q and R are connected, then p and R are also connected.
In pairs of integers, only two objects connected belong to the same equivalence class. Our goal is to write a program that filters out all the meaningless pairs of integers in a sequence (both integers come from the same equivalence class). To achieve the desired effect, we need to design a data structure that holds enough information about all the pairs of integers known and can be used to determine connectivity. These problems are collectively referred to as dynamic connectivity problems.
Union-find data type (API)
pubic class UF
UF(int N) – initialize union-find data structure with N objects(0 – N – 1)
void union(int p, int q) – add connection between p and q
boolean connected(int p, int q) – are p and q in the sanme component?
int find(int p) – component indentifier for p (0 – N – 1)
int count() – number of components
The template is as follows:
public class UF {
private int[] id; / / component id
private int count; // The number of components
/**
* intialize
* @paramN components times PI over PI
public UF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count(a) {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/** * different algorithms will use different search and connection methods */
public int find(int p) {}
public void union(int p, int q) {}}Copy the codeDynamic-connectivity client
public class DynamicConnectivityClient {
public static void main(String[] args) {
int N = StdIn.readInt();
UF uf = new UF(N); // initialize
while(! StdIn.isEmpty()) {int p = StdIn.readInt();
int q = StdIn.readInt();
if(! uf.connected(p, q)) { uf.union(p, q); StdOut.println(p +""+ q); }}}}Copy the code2. Quick find
Fast lookup can reduce the search time complexity to O(1) constant.
Use the array int[N] ID to record whether two contacts exist in the same connected component.
The same ID value indicates the same connected component.
public class QuickFindUF {
private int[] id;
private int count; // The number of components
public QuickFindUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count(a) {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// find p
public int find(int p) {
return id[p];
}
public void union(int p, int q) {
int pId = find(p);
int qId = find(q);
for (int i = 0; i < id.length; i++) {
if(id[i] == pId) id[i] = qId; } count--; }}Copy the codeTime complexity
find()–O(1)union()–O(N)
3. Quickly merge Quick Union
Fast merging, using the idea of “tree”, connected components are all in the same tree.
In order to determine whether they are in the same connected component, we only need to see whether their root nodes are the same.
The union() operation simply joins the root of the node to be joined to the root of another tree.
public class QuickUnionUF {
private int[] id;
private int count;
public QuickUnionUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count(a) {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// find the root of p. The root node is itself
public int find(int p) {
while(p ! = id[p]) p = id[p];return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return; id[pRoot] = qRoot; count--; }}Copy the codeTime complexity
find()The time complexity of the operation is at worstO(N).union()The time complexity of the operation is at worstO(1).
4. Fast merge Weighted Quick Union with weights
The qick-find algorithm above, in the worst case, will eventually form a very tall tree in the connected process, resulting in the time complexity of union() operation from constant to O(n), the effect is very poor, find() is also O(n).
Therefore, in the process of merging trees, we need to weigh the depth of the two trees. Here, we add an array size[N] to the data structure to record the total number of nodes contained in the tree with the current subscript node as the root node.
When you do a union() operation, you should compare weights, and then have the heavier tree as the root and the lower-weight tree as the root. The resulting new tree is thus guaranteed to be smaller in height.
Note: The two nodes compared above are root nodes of nodes to be connected.
public class WeightedQuickUnionUF {
private int[] id;
private int[] size; // The weight of the tree with the current index as the root node (total number of nodes)
private int count;
public WeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1; // Start as the root node with a weight of 1}}public int count(a) {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
while(p ! = id[p]) p = id[p];return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
// The lower weight tree is connected to the higher weight tree
if (size[pRoot] < size[qRoot]) {
id[pRoot] = qRoot;
size[qRoot] += size[pRoot];
} else{ id[qRoot] = pRoot; size[pRoot] += size[qRoot]; } count--; }}Copy the codeTime complexity analysis
find()The time complexity of the operation is at worstO(lgN). The reason is that we connect the connected set containing fewer objects to the connected set containing larger objects each time, so the height of the connected set generated in the worst case isO(lgN).union()The time complexity of the operation is at worstO(lgN). The causes andfind()The same.
5. Quick-Union with path compression
On a normal quick-union basis, in the process of finding the root node find(), the parent node is found in each loop until the root node is found. In each loop, the subtree is directly connected to the root node, so that the depth of the subtree below is reduced, and the height of the whole tree is reduced.
Only find() needs to be changed
public class QuickUnionPathCompressionUF {
private int[] id;
private int count;
public QuickUnionPathCompressionUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public int count(a) {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
int root = p;
while(root ! = id[root]) root = id[root];// Find the current connected component root node
while(id[p] ! = root) {int temp = p; // Save the current location
p = id[p]; // Point the current cursor to the parent node
id[temp] = root; // The bottom child node points directly to the root node
}
return root;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return; id[pRoot] = qRoot; count--; }}Copy the codeWeighted quick-union with path compresson
Find ();
public class WeightedQuickUnionByHeightUF {
private int[] id;
private int[] size;
private int count;
public WeightedQuickUnionByHeightUF(int N) {
count = N;
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1; }}public int count(a) {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
int root = p;
while(root ! = id[root]) root = id[root];// Find the root node
while(id[p] ! = root) {int temp = p; // If the cursor moves up, the subtree connects directly to the root node
p = id[p];
id[temp] = root;
}
return root;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
if (size[pRoot] < size[qRoot]) {
id[pRoot] = qRoot;
size[qRoot] += size[pRoot];
} else{ id[qRoot] = pRoot; size[pRoot] += size[qRoot]; } count--; }}Copy the code