Number of Connected Components (Provinces)

Problem Overview
The "Number of Connected Components (Provinces)" is LeetCode problem 547, commonly asked in Microsoft interviews with tags Graph, DFS, BFS, and Union Find. It involves counting connected components in an undirected graph represented as an adjacency matrix.[1][3][5]

Full Problem Statement
Given an n x n binary matrix isConnected where isConnected[i][j] == 1 means the ith city and jth city are directly connected, and isConnected[i][j] == 0 otherwise. The matrix is symmetric (isConnected[i][j] == isConnected[j][i]) and isConnected[i][i] == 1 for all i. Return the number of provinces (connected components, considering direct and indirect connections).[5][9][1]

Constraints

• 1 <= n <= 200
• isConnected[i][i] == 1 for all 0 <= i < n
• isConnected[i][j] == isConnected[j][i] == 1 or 0 for all i, j
• Input is a well-formed n x n matrix.[3][7][1]

Input/Output Examples

Example 1
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Explanation: Cities 0 and 1 form one province; city 2 forms another.[9][1]

Example 2 (from typical walkthroughs)
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: Each city is isolated, forming three provinces.[3]

Example 3 (inferred from discussions)
Input: isConnected = [[1,1,1],[1,1,1],[1,1,1]]
Output: 1
Explanation: All cities are connected, forming one province.[7][1]