Categories: Graph/Union Find

Level: Medium**

Introduction: (Basic + Advanced + Interview Edition) 
Learning Algorithms from LeetCode + Interview Success Guide 
(Regular price: 3591 NTD, Discounted price until 2023/06/30 23:59)
https://hiskio.com/bundles/eCP23B397?s=tc

(Regular price: 3990 NTD, Valid for a long term) 
https://bit.ly/lc2022all

Please help me click on the “SHOW EMBED” below and give it 5 likes~ If you like it, you can also give me a round of applause~ 
(Liking doesn’t cost anything, thank you for supporting my writing~)

Question

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of *provinces *.

Example 1

1
2

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2

1
2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

Analysis/Approach:

There are n cities, some of which are directly connected to each other, while others are not. If city a is directly connected to city b, and city b is directly connected to city c, then city a is indirectly connected to city c. (That’s a lot of unnecessary words LOL)

A province is a group of cities that are directly or indirectly connected, and there are no other cities in this group. (In other words, if you can walk from x to y, they are considered part of the same province).

Given an n x n matrix isConnected, where isConnected[i][j] = 1 means the ith city is directly connected to the jth city, and isConnected[i][j] = 0 means they are not directly connected, return the total number of provinces.

We have discussed many concepts related to graphs in Article 115 and the previous article. Today, let’s take a closer look at the usage of Union Find.

Since the variable name “isConnected” is too long, we will use “edges” to refer to it for convenience.

First, we need to find the number of provinces, which is another typical scenario where Union Find can be used. However, as we mentioned before, if we only trace back along the edges to find the root, the find operation for a single point can potentially take O(n) time. Therefore, we need to simplify the process by performing ** path compression** during the ** union** operation.

In the union operation, instead of arbitrary assignment as before, we can now choose to check which root has a higher rank and merge the group with the lower rank into the group with the higher rank. The root of the group with the lower rank should be set as the root of the group with the higher rank. This way, during the union process, since we always merge the smaller group into the larger one, it will be less likely to create long chains of connections. This technique is called path compression .

Therefore, our implementation of the find operation and union operation will look like this:

find(root, i) :

1. Initialize r as root[i]
2. If r and root[r] are not equal (indicating that we haven’t reached the node that is the root), enter the loop:
3. Set root[r] as root[root[r]]
4. Set r as root[r] (move up one level and continue the evaluation)
5. After the loop (steps 2–4) ends, set root[i] as r, indicating that the topmost leader of node i is r.

union(root, rank, x, y):

1. Apply the find operation to x and y separately to obtain their respective roots rx and ry .
2. If rx and ry are the same , it means they are already in the same group, so return false .
3. If they are different, compare the ranks rank[rx] and rank[ry]:

• If rank[rx] ≥ rank[ry] , increase rank[rx] by rank[ry] and set root[ry] as rx .
• Otherwise, if rank[rx] < rank[ry] , increase rank[ry] by rank[rx] and set root[rx] as ry .

After initializing root and rank (from 1 to n-1 and ** 1**), we can use a nested loop to call the union operation for the pairs of cities that are connected by edges. Finally, we iterate through each node and perform the find operation to determine the ** unique roots** and store them in a HashSet. The answer can be obtained by checking the size of the HashSet.

Here is an implementation in Java:

Java

We can use Arrays.fill() to set values in Java. Since we don’t specifically need the true/false return value for the union operation, we can change its return type to void and modify the necessary parts accordingly. Finally, we can use a HashSet to record the answers, iterate through i, call find(), and add the results. The final answer can be obtained by checking the size of the HashSet.

Notice that you could start j from i+1 rather than 0.

Python

In Python, the implementation is similar except for the use of sub-functions.

Potential Interview Questions:
“What are the time and space complexities?”
(O(n²)/O(n), as even with path compression, traversing all edges still takes O(n²) time, and the space complexity only needs to consider the space for recording roots and ranks.)

Similar and Extended Topics: 0684. Redundant Connection (Medium)

Special thanks to suggestions/corrections from viewers:
(Welcome to provide feedback to help with corrections~)

Learn Algorithms from LeetCode — See you next time!

Want to see more problems? 
Feel free to check out Article 0 for the topic you want!

Also, follow our Facebook page for notifications on new articles:
Learn with Desolve