So you decided to take it one step further, huh? Instead of settling with Array and maybe LinkedList.
Although there’s nothing wrong just knowing the basic ones, you still can be a solid developer.
But if you ever want to be a engineer, let’s dive in:
Step 0. Why? (Skip to Step 1 if you are a professional)
What exactly is UnionFind and why do we need it?
Remember Audible and Amazon, eh?
Now who’s the boss?
Yes! Audible belongs to Amazon.
Ok this sounds far too simple, we can just get a HashMap, and just point the Audible to its parent.
Well well well, imagine you are in a system design and need to point thousands of employees to their parent, hmm?
Oh and make it more challenging let’s say the companies are merging and selling all the time.
Great! You agreed we need something efficient and professional.
Step 1. How?
So for professionals I am telling you outright that UnionFind actually is tree.
You were right, using a HashMap or Array would do the job but we need a little delicate path compression and trust me this data structure is full of traps that you can make it full of bugs easily if careless, or even just tired.
For the sake of brevity we are using a simple primitive Java array. (You can swap it with a HashMap easily).
- 1.1. Constructor
We are simply pointing everybody to himself. Meaning everyone is a disconnected dot. Audible belongs to Audible meaning it is not yet acquired by any other company.
public ConnectingGraph_589(int n) {
// do intialization if necessary
father = new int[n + 1];
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
- 1.2. Connect
Connect two companies together. e.g. pointing Audible as the son of Amazon. Meaning Amazon acquires Audible.
public void connect(int a, int b) {
// write your code here
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
father[rootA] = rootB;
}
}
- 1.3. Query
Check if the two companies belong to the same corporation.
This means returning true if Audible and Amazon has the same BIG brother — Amazon.
Or let’s say returning true if Nokia and Microsoft has the same BIG brother — the MS.
public boolean query(int a, int b) {
// write your code here
return find(a) == find(b);
}
- 1.4 Find
This is the best part of the data structure in that you recursively find the BIG brother and update every children in the meanwhile.
private int find(int x) {
if (father[x] == x) {
return x;
} else {
return father[x] = find(father[x]);
}
}
Last Step, show me the code:
public class ConnectingGraph_589 {
private int[] father;
/*
* @param n: An integer
*/
public ConnectingGraph_589(int n) {
// do intialization if necessary
father = new int[n + 1];
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
/*
* @param a: An integer
* @param b: An integer
* @return: nothing
*/
public void connect(int a, int b) {
// write your code here
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
father[rootA] = rootB;
}
}
/*
* @param a: An integer
* @param b: An integer
* @return: A boolean
*/
public boolean query(int a, int b) {
// write your code here
return find(a) == find(b);
}
private int find(int x) {
if (father[x] == x) {
return x;
} else {
return father[x] = find(father[x]);
}
}
}
For more algorithms feel free to check out my Github https://github.com/oliverwreath/JiuZhang.git
