Practice/Amazon/Leetcode 547. Number of Provinces

Leetcode 547. Number of Provinces

CodingMust

Problem

You are given information about a computer network represented as a square matrix. The matrix networks is of size n x n, where n is the total number of computers. Each cell networks[i][j] tells you whether computer i and computer j are directly connected:

• networks[i][j] = 1 means computers i and j are directly connected
• networks[i][j] = 0 means computers i and j are not directly connected
• networks[i][i] = 1 always (a computer is considered connected to itself)

Two computers belong to the same network if they can communicate either directly or through other computers as intermediaries. Your task is to determine how many separate networks exist.

Requirements

1. Count the total number of distinct networks
2. Computers in the same network can be connected directly or indirectly through other computers
3. A single isolated computer counts as one network
4. The connection matrix is symmetric: if computer A connects to computer B, then B connects to A

Constraints

• 1 ≤ n ≤ 200
• networks[i][j] is either 0 or 1
• networks[i][i] = 1 for all valid i
• networks[i][j] = networks[j][i] (symmetric matrix)

Examples

Example 1:

Input: networks = [[1,1,0],[1,1,0],[0,0,1]] Output: 2 Explanation: Computer 0 and computer 1 are directly connected, forming one network. Computer 2 is not connected to any other computer, forming a second network.

Example 2:

Input: networks = [[1,0,0],[0,1,0],[0,0,1]] Output: 3 Explanation: No connections exist between different computers. Each computer forms its own isolated network.

Example 3:

Input: networks = [[1,1,1],[1,1,1],[1,1,1]] Output: 1 Explanation: All computers are directly connected to each other, forming one large network.