/**
* 547. Number of Provinces
* 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
*/
See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/trees/FriendCircles.java
Also included in the explanations is a solution to a very similar problem to this ‘Stones Removed’; on github its available at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/graph/StonesRemoved.java
This question is same as that of StonesRemoved. In below code we applied DFS, StonesRemoved was done via union find. Union find will be more efficient than dfs. The below approach will run in O(N^2) whereas union find runs in O(n log(n)).
Algorithm:
- Iterate through the people increment the group count if the person has so far not been visited
- Logic is that each group of connected people will be processed per iteration of the person loop in findCircleNum method below. For all people that are connected to a given person run a dfs to connect them while updating the visited set per iteration.
- In the end the count being incremented in 1 will identify distinct groups.
Here is the code:
void dfs(int i, int[][] p, int people, Set<Integer> visited) {
visited.add(i);
for (int j = 0; j < people; j++) {
//note that we are checking the row of person passed as first argument.
//this ensures that once we find a person who is friend of current person
//we can dfs through that person's friends.
if (i != j && p[i][j] == 1 && !visited.contains(j)) {
dfs(j, p, people, visited);
}
}
}