Number of Provinces
Application of Union Find / Disjoint Set Union Data Structure

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
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 UnionFind Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of UnionFind and become really good at solving problems using UnionFind.
Please have a very good understanding of UnionFind 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 UnionFind based solution for even a complex problem when you are familiar with the implementation of UnionFind data structure discussed in the Template section of UnionFind 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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Implementation:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Complexity Analysis:
Time Complexity: O(3 * N * InverseAckermann(N)) = O(N) since InverseAckermann(N) = O(1) approximatelySpace 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
UnionFind .
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn