Algorithm

A province is a group of directly or indirectly connected cities and no other cities outside of the group. That means, if we traverse from any one city then we can reach to all the cities in that province.

We know about both the traversals, Breadth First Search (BFS) and Depth First Search (DFS). We can use any of the traversals to solve this problem because a traversal algorithm visits all the nodes in a graph. In any traversal technique, we have one starting node and it traverses all the nodes in the graph. Suppose there are ‘N’ number of provinces so we need to call the traversal algorithm ‘N‘ times, i.e., there will be ‘N’ starting nodes. Hence, we just need to figure out the number of starting nodes.

Create a visited array to keep track of all the cities that are visited.
Run a loop from 0 to N, and call the DFS for the every unvisited node.
DFS function call will make sure that it starts the DFS call from that unvisited node, and visits all the nodes that are in that province, and at the same time, it will also mark them as visited.
Keep repeating these steps, for every node that you find unvisited, and visit the entire province.
Add a counter to count the number of times the DFS function is called, as in this way we can count the total number of starting nodes, which will give us the number of provinces.