Friend Circles

Given an adjacency matrix of an undirected graph, return the number of connected components (provinces). Pattern focus: Adjacency List. Convert the matrix representation to traversal-friendly neighbors or scan it carefully to discover components.

Input Format

isConnected = adjacency matrix of an undirected graph

Output Format

number of connected components

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • isConnected must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output:

2

Explanation:

Nodes {0,1} form one province and node 2 forms another.

Example 2:

Input:

isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output:

3

Explanation:

Each node is isolated.

Loading...
Friend Circles - Graph Fundamentals DSA Problem