Hello! In this session, we will learn about one of the algorithms frequently encountered in coding tests: Union-Find. This algorithm is useful for finding connected components in a graph or managing sets, and is utilized in various problem-solving scenarios. Before we begin, let’s understand the basic concept of Union-Find and learn specific applications through real problem-solving processes.
What is Union-Find?
Union-Find is a data structure that tracks how given elements are divided into connected sets. It provides the following two operations:
- Find: An operation to find which set a given element belongs to.
- Union: An operation to combine two sets.
This data structure is useful for finding connected components in a graph and is often used to determine the presence of cycles. Union-Find boasts very fast execution times by utilizing optimization techniques.
Problem Description
Now, let’s introduce a problem where we can apply Union-Find. We have the following problem:
Problem: Finding Friends
There are n people. Each person can make friends, and the friendship relationship is mutual. Write an algorithm that can determine whether two people are friends based on a given list of friendship relationships. The friendship relationships are given in the following format:
[[1, 2], [2, 3], [4, 5]]In the above example, 1 and 2 are friends, and 2 and 3 are friends, which means 1 and 3 are indirectly friends. 4 and 5 are separate friendships, so 1 and 4 are not friends. For each query, check if the two people are friends.
Implementing the Union-Find Algorithm
Now, let’s examine how to solve this problem using the Union-Find algorithm. First, we’ll define a Union-Find structure and implement the necessary functions.
class UnionFind {
constructor(size) {
this.parent = new Array(size);
this.rank = new Array(size).fill(1);
for (let i = 0; i < size; i++) {
this.parent[i] = i;
}
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
// Union by rank
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
}
areConnected(x, y) {
return this.find(x) === this.find(y);
}
}
Problem-Solving Process
1. Process the input of the problem. Receive the friendship relationships and take the targets for performing the promised queries.
function processFriendships(friendships, queries, numberOfPeople) {
const uf = new UnionFind(numberOfPeople + 1); // +1 to accommodate 1-indexed people
friendships.forEach(([a, b]) => {
uf.union(a, b);
});
return queries.map(([x, y]) => uf.areConnected(x, y));
}
2. Iterate through the list of friendships and perform the union operation for each pair.
3. For each query, determine whether the two people belong to the same set.
Final Code
const friendships = [[1, 2], [2, 3], [4, 5]];
const queries = [[1, 3], [1, 4], [4, 5]];
const numberOfPeople = 5;
const results = processFriendships(friendships, queries, numberOfPeople);
console.log(results); // [true, false, true]
Interpreting Results
The final query results are as follows:
- 1 and 3 are friends: true
- 1 and 4 are not friends: false
- 4 and 5 are friends: true
The above code efficiently handles friendship relationships using Union-Find. Union-Find is particularly useful when there are many sets, and its time complexity is nearly constant time.
Conclusion
In this lecture, we solved the friend-finding problem using the Union-Find algorithm. Union-Find can be applied to various problems and is a very useful tool for solving algorithmic challenges. Continue to learn and practice various algorithms to achieve good results in coding tests!
Thank you!