Count Similar Photo Groups

You are given n photos labeled 0 to n - 1 and an n x n binary matrix isSimilar.

• isSimilar[i][j] = 1 means photo i and photo j are directly similar.
• isSimilar[i][j] = 0 means they are not directly similar.

Similarity is also transitive: if photo A is similar to B, and B is similar to C, then A is considered similar to C even if A and C are not directly similar.

Treat each set of directly or indirectly similar photos as one photo group.

Return the total number of photo groups.

You may assume the similarity relationship is symmetric, so if isSimilar[i][j] = 1, then isSimilar[j][i] = 1.

Count Similar Photo Groups

You are given a binary matrix isSimilar representing similarity relationships among photos. Photo indices range from 0 to n - 1, where n is the number of photos.

• isSimilar[i][j] = 1 means photo i and photo j are directly similar.
• isSimilar[i][j] = 0 means they are not directly similar.

Similarity is transitive: if photo A is similar to B, and B is similar to C, then A and C belong to the same group even if isSimilar[A][C] = 0.

Treat each set of directly or indirectly similar photos as one photo group.

Return the total number of photo groups.

If the input matrix is empty, return 0.

Constraints

• 0 <= n <= 200
• isSimilar is an n x n matrix
• Each value in isSimilar is either 0 or 1
• isSimilar[i][j] == isSimilar[j][i] for all valid i, j

Examples

Example 1

Input: []
Output: 0

Explanation: There are no photos, so there are no groups.

Example 2

Input: [[1]]
Output: 1

Explanation: A single photo forms one group by itself.

Hints

1. Think of each photo as a node in an undirected graph, and each 1 as an edge.
2. Count how many times you need to start a new DFS or BFS from an unvisited photo.