Number of Provinces
BFS & DFS Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Find the number of provinces (connected components) in an undirected graph given as an adjacency matrix., Graph, Undirected Graph, Adjacency Matrix, Adjacency List, Graph Traversal, Depth-First Search, Breadth-First Search, Recursion, Arrays, Time Complexity, Space Complexity, Connected Components, graph representation, graph components, visited tracking, dfs, graph traversal, bfs.
Number of Provinces Problem Statement Given an undirected graph with V vertices, find the total number of provinces. A province is a group of directly or indirectly connected cities. If there is a path between two vertices u and v, they belong to the same province. Input Specification The first line contains a single integer V, representing the number of vertices in the graph. The next V lines represent the adjacency matrix of the graph. Each line contains V integers, where adj[i][j] = 1 indicates a direct connection between city i and city j, and adj[i][j] = 0 otherwise. It is guaranteed that adj[i][i] = 1 (a city is connected to itself) and adj[i][j] = adj[j][i] (connections are undirected). Output Specification Return an integer representing the number of provinces. Constraints Constraints were not provided in the original content. Sample Test Case Input: Output: Explanation: Cities 0 and 2 are connected. They form one province: {0, 2}. City 1 is isolated. It forms another province: {1}. Total provinces: 2.