Problem Statement: Given an undirected graph with V vertices. We say two vertices u and v belong to a single province if there is a path from u to v or v to u. Your task is to find the number of provinces.
Note: A province is a group of directly or indirectly connected cities and no other cities outside the group.
Pre-requisite: Disjoint Set data structure
Example 1:
Input Format:
Example 2:
Input Format:
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
A province is a group of directly or indirectly connected cities and no other cities outside the group. Considering the above example, we can go from 1 to 2 as well as to 3, from every other node in a province we can go to each other. As we cannot go from 2 to 4 so it is not a province.
So, basically, we need to find the number of connected components of the given graph. We have previously solved this problem using traversal techniques with the concept of connected components.
In this article, we are going to solve this problem using the Disjoint Set data structure. Generally, the graph in this problem is given in the form of an adjacency matrix where matrix[i][j] = 1 means that there is an edge between node i and node j.
If we apply the union method to the 2nd example, the graph will look like the following:
Here node 1 is the ultimate parent for nodes 1, 2, and 3, node 4 is the ultimate parent of nodes 4 and 5, and node 6 is the ultimate parent for nodes 6 and 7.
Approach:
Here, our objective is to find the number of connected components. Now, if we just carefully observe the number of ultimate parents is the same as the number of connected components. So, instead of counting the number of connected components, we will count the number of ultimate parents.
We can find the number of ultimate parents, by finding the ultimate parent for each particular node and counting the unique ultimate parents.
For example, in the 2nd example, if we apply the method the result will be the following:
findUPar(1) = 1, findUPar(2) = 1, findUPar(3) = 1, findUPar(4) = 4, findUPar(5) = 4, findUPar(6) = 6, findUPar(7) = 6, where findUPar() signifies the find ultimate parent function. So, the number of unique parents is 3.
Observation:
We can optimize the above method using the observation that a particular is an ultimate parent only when the node itself is its ultimate parent. For example, if findUPar(1) = 1, node 1 is one of the ultimate parents.
Note: The intuition is to count the number of nodes for which the nodes themselves are their ultimate parents.
The algorithm steps are as follows:
- First, we need to apply the union method(either unionByRank(i, j) or unionBySize(i, j)) between the nodes i and j if the adjacency marix[i][j] = 1. We need not perform union(j, i) as it will be automatically discarded.
- Then we need to run a loop from the starting node to N(total no. of nodes).
- Inside that loop, we will check if the ultimate parent of a node is the node itself. If we find so, we will increase the counter variable by 1.
The checking can be done using either the findUPar() method or using the parent array (inside the Disjoint Set data structure) that is storing the ultimate parent for all the nodes. The time complexity for both cases is similar(i.e. constant). - Finally, the counter variable will be the answer.
Note: If you wish to see the dry run of the above approach, you can watch the video attached to this article.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
//User function Template for C++
class DisjointSet {
public:
vector<int> rank, parent, size;
DisjointSet(int n) {
rank.resize(n + 1, 0);
parent.resize(n + 1);
size.resize(n + 1);
for (int i = 0; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int findUPar(int node) {
if (node == parent[node])
return node;
return parent[node] = findUPar(parent[node]);
}
void unionByRank(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (rank[ulp_u] < rank[ulp_v]) {
parent[ulp_u] = ulp_v;
}
else if (rank[ulp_v] < rank[ulp_u]) {
parent[ulp_v] = ulp_u;
}
else {
parent[ulp_v] = ulp_u;
rank[ulp_u]++;
}
}
void unionBySize(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (size[ulp_u] < size[ulp_v]) {
parent[ulp_u] = ulp_v;
size[ulp_v] += size[ulp_u];
}
else {
parent[ulp_v] = ulp_u;
size[ulp_u] += size[ulp_v];
}
}
};
class Solution {
public:
int numProvinces(vector<vector<int>> adj, int V) {
DisjointSet ds(V);
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (adj[i][j] == 1) {
// i and j
ds.unionBySize(i, j);
}
}
}
int cnt = 0;
for (int i = 0; i < V; i++) {
if (ds.parent[i] == i) cnt++;
}
return cnt;
}
};
int main() {
int V = 3;
vector<vector<int>> adj = {{1, 0, 1}, {0, 1, 0}, {1, 0, 1}};
Solution obj;
int ans = obj.numProvinces(adj, V);
cout << "The number of provinces is: " << ans << endl;
return 0;
}
Output: The number of provinces is: 2 (Output for 1st example)
Time Complexity: O(N2)+O(N* 4α) ~ O(N2)+O(N) where N = no. of nodes. O(N2) for visiting the adjacency matrix and O(N) for the counting of ultimate parents. 4α is so small that this term can be ignored.
Space Complexity: O(2N), where N = no. of nodes. O(2N) for the two arrays parent and size(or rank) of size N.
Java Code
import java.io.*;
import java.util.*;
//User function Template for Java
class DisjointSet {
List<Integer> rank = new ArrayList<>();
List<Integer> parent = new ArrayList<>();
List<Integer> size = new ArrayList<>();
public DisjointSet(int n) {
for (int i = 0; i <= n; i++) {
rank.add(0);
parent.add(i);
size.add(1);
}
}
public int findUPar(int node) {
if (node == parent.get(node)) {
return node;
}
int ulp = findUPar(parent.get(node));
parent.set(node, ulp);
return parent.get(node);
}
public void unionByRank(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (rank.get(ulp_u) < rank.get(ulp_v)) {
parent.set(ulp_u, ulp_v);
} else if (rank.get(ulp_v) < rank.get(ulp_u)) {
parent.set(ulp_v, ulp_u);
} else {
parent.set(ulp_v, ulp_u);
int rankU = rank.get(ulp_u);
rank.set(ulp_u, rankU + 1);
}
}
public void unionBySize(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (size.get(ulp_u) < size.get(ulp_v)) {
parent.set(ulp_u, ulp_v);
size.set(ulp_v, size.get(ulp_v) + size.get(ulp_u));
} else {
parent.set(ulp_v, ulp_u);
size.set(ulp_u, size.get(ulp_u) + size.get(ulp_v));
}
}
}
class Solution {
static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {
DisjointSet ds = new DisjointSet(V);
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (adj.get(i).get(j) == 1) {
// i and j
ds.unionBySize(i, j);
}
}
}
int cnt = 0;
for (int i = 0; i < V; i++) {
if (ds.parent.get(i) == i) cnt++;
}
return cnt;
}
}
class Main {
public static void main (String[] args) {
int V = 3;
ArrayList<ArrayList<Integer>> adj = new ArrayList<>() {
{
add(new ArrayList<Integer>(Arrays.asList(1, 0, 1)));
add(new ArrayList<Integer>(Arrays.asList(0, 1, 0)));
add(new ArrayList<Integer>(Arrays.asList(1, 0, 1)));
}
};
Solution obj = new Solution();
int ans = obj.numProvinces(adj, V);
System.out.println("The number of provinces is: " + ans);
}
}
Output: The number of provinces is: 2 (Output for 1st example)
Time Complexity: O(N2)+O(N* 4α) ~ O(N2)+O(N) where N = no. of nodes. O(N2) for visiting the adjacency matrix and O(N) for the counting of ultimate parents. 4α is so small that this term can be ignored.
Space Complexity: O(2N), where N = no. of nodes. O(2N) for the two arrays parent and size(or rank) of size N.
Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]