Number of Provinces

Application of Union Find / Disjoint Set Union Data Structure


Problem Statement:


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:
Input: isConnected = [ 
[1,1,0],
[1,1,0],
[0,0,1]

]
Output: 2

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

]
Output: 3

Note: This problem is part of Union-Find Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of Union-Find and become really good at solving problems using Union-Find.

Please have a very good understanding of Union-Find Fundamentals before solving this problem. Through all the problems discussed in Problem Solving using Union Find one of my goals is to show you how easy it becomes writing an Union-Find based solution for even a complex problem when you are familiar with the implementation of Union-Find data structure discussed in the Template section of Union-Find Fundamentals chapter.

Solution:


All the connected cities cities would form a connected component or disjoint set. So if there are N provinces, there would actually be N connected components or disjoint sets. So the problem reduces to finding all the connected components or disjoint sets. We could achieve this very efficiently by using Union Find data structure.
Whenever we find two cities are connected we would unionize them. Once we have processed all the cities, we return the total number of connected components or disjoint sets.

The code below efficiently implements the above algorithm.

Java Implementation:



Login to Access Content



Python Implementation:



Login to Access Content




Complexity Analysis:

Time Complexity: O(3 * N * Inverse-Ackermann(N)) = O(N) since Inverse-Ackermann(N) = O(1) approximately

Space Complexity: O(N) since we need to store N cities in union find data structure where N = total number of cities. In time complexity we 3N because the given isConnected array is of dimension N X 3.

Please be sure to take a serious look at all the problems discussed in Union Find Problems to become from good to GREAT in solving problems using Union-Find .



Instructor:

Abhishek Dey

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.


Help Your Friends save 40% on our products

wave