Number of Provinces

Given a V × V adjacency matrix adj for an undirected graph of cities, return the number of provinces. A province contains every city reachable from one of its…

Given a V × V adjacency matrix adj for an undirected graph of cities, return the number of provinces. A province contains every city reachable from one of its cities through direct connections or paths through intermediate cities, and no cities outside that group. adj[i][j] is 1 when cities i and j are directly connected and 0 otherwise. Cities are indexed from 0 to V − 1. The matrix is symmetric and each diagonal entry is 1.

- 1 <= V <= 300 - adj has V rows and V columns - adj[i][j] is the integer 0 or 1 - adj[i][i] == 1 - adj[i][j] == adj[j][i] - The preset visualizer shows graphs up to 10 cities; larger valid graphs are execution-only.

Example 1: input adj = [[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]]; output 2. Cities {0,3} form one province and cities {1,2} form another. No path connects the two groups.

Example 2: input adj = [[1,1,0],[1,1,1],[0,1,1]]; output 1. City 0 reaches city 2 through city 1. Every city belongs to one province, even though adj[0][2] is 0.

Category: Graphs. Topic: graph. Difficulty: Medium. Patterns: graph-traversal.