Katkat
Back

Count Connected Groups in a Relationship Matrix

VisaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Determine the number of connected components in an undirected graph represented by an adjacency matrix, accounting for transitive relationships.

Problem Statement

A financial platform monitors relationships between user accounts to detect organized activity. Relationships are provided as an n x n symmetric binary matrix related, where:

  • related[i][j] = 1 indicates that account i and account j share a direct connection.
  • related[i][j] = 0 indicates no direct connection.
  • related[i][i] = 1 for all i (every account is connected to itself).

Connections are transitive: if account A is connected to account B, and account B is connected to account C, then A and C belong to the same group. A connected group is a maximal subset of accounts such that every account in the subset is connected (directly or transitively) to every other account in the subset.

Write a function that returns the total number of connected groups.

Function Signature

def countConnectedGroups(related: list[list[int]]) -> int:
    pass

Input & Output Format

  • Input: A 2D integer array related of size n x n containing only 0s and 1s.
  • Output: An integer representing the total count of connected groups.

Constraints

  • 1 <= n <= 300
  • len(related) == n and len(related[i]) == n for all 0 <= i < n
  • related[i][j] is either 0 or 1
  • related[i][i] == 1 for all 0 <= i < n
  • related[i][j] == related[j][i] for all 0 <= i, j < n

Examples

Example 1

Input: related = [
  [1, 1, 0],
  [1, 1, 0],
  [0, 0, 1]
]
Output: 2
Explanation:
Account 0 and account 1 are directly connected, forming group {0, 1}.
Account 2 is isolated, forming group {2}.
Total groups: 2.

Example 2

Input: related = [
  [1, 1, 0, 0],
  [1, 1, 1, 0],
  [0, 1, 1, 0],
  [0, 0, 0, 1]
]
Output: 2
Explanation:
Account 0 is connected to 1, and 1 is connected to 2. Through transitivity, accounts {0, 1, 2} form one connected group.
Account 3 is isolated, forming group {3}.
Total groups: 2.

Edge Cases to Consider

  • n = 1: The answer is always 1.
  • Fully connected matrix (all entries 1): The answer is 1.
  • Fully disconnected matrix (identity matrix): The answer is n.

Hints

Hint 1

Model the problem as finding the number of connected components in an undirected graph where nodes are indices 0 to n - 1.

Hint 2

Transitivity implies that simple neighbor counts are insufficient; you must traverse all reachable nodes from an unvisited node using BFS, DFS, or Union-Find.

Hint 3

Because the input is an adjacency matrix, visiting each node requires scanning its row of length n, resulting in an O(n^2) overall traversal.

Follow-up questions

  • What is the theoretical time complexity difference between DFS and Disjoint Set Union (DSU) when given an adjacency matrix versus an adjacency list?
  • How would your solution adapt if relationships were streamed one pair at a time rather than provided upfront as a static matrix?
  • If relationships were asymmetric (directed) and groups required mutual reachability, which algorithm would you use to find the components?