262. Number of provinces
Given an undirected graph with V vertices. Two vertices u and v belong to a single province if there is a path from u to v or v to u. Find the number of provinces. The graph is given as an n x n matrix adj where adj[i][j] = 1 if the ith city and the jth city are directly connected, and adj[i][j] = 0 otherwise.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
Example 1:
Input: adj=[ [1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1] ]
Output: 2
Explanation:In this graph, there are two provinces: [1, 4] and [2, 3]. City 1 and city 4 have a path between them, and city 2 and city 3 also have a path between them. There is no path between any city in province 1 and any city in province 2.
Example 2:
Input: adj= [ [1, 0, 1], [0, 1, 0], [1, 0, 1] ]
Output: 2
Explanation: The graph clearly has 2 Provinces [1,3] and [2]. As city 1 and city 3 has a path between them they belong to a single province. City 2 has no path to city 1 or city 3 hence it belongs to another province.
Now Your Turn!
Pick the correct output for the given inputInput: adj= [ [1, 1], [1, 1] ]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- Â Â 1 <= V <= 300
- Â Â V == adj.length
- Â Â V == adj[i].length
- Â Â adj[i][j] is 1 or 0.
- Â Â adj[i][i] == 1
- Â Â a[i][j] == adj[j][i]