Detect Connected Account Clusters
At PhonePe, understanding the relationships between user accounts is paramount for various functions, including fraud detection, risk assessment, and personalized service delivery. When suspicious activities link accounts, it's crucial to identify all indirectly connected accounts to form 'clusters'. These clusters can indicate coordinated behavior or shared vulnerabilities.
This problem challenges you to implement an efficient algorithm to identify and count the total number of distinct connected account clusters based on a given set of direct linkages.
Your task is to implement a function detectConnectedAccountClusters that takes a list of unique account IDs and a list of direct linkages between these accounts. You need to determine the total number of distinct groups (clusters) of accounts, where two accounts are considered to be in the same cluster if they are directly or indirectly linked.
accounts: An array of unique string IDs, each representing a user account. All accounts involved in linkages will be present in this array.linkages: An array of pairs [account_id_A, account_id_B]. Each pair signifies a direct linkage between account_id_A and account_id_B (e.g., through a suspicious transaction or shared activity).account_id_A and account_id_B in a linkage pair does not matter; the linkage is bidirectional.account_ids mentioned in linkages are guaranteed to exist in the accounts array.Examples
Example 1
Input:
accounts = ["A1", "A2", "A3", "A4", "A5"], linkages = [["A1", "A2"], ["A3", "A4"]]
Output:
3
Note:
Accounts A1 and A2 form one cluster. Accounts A3 and A4 form another. Account A5 is standalone. Total 3 distinct clusters.
Example 2
Input:
accounts = ["U1", "U2", "U3", "U4", "U5", "U6"], linkages = [["U1", "U2"], ["U2", "U3"], ["U4", "U5"], ["U6", "U4"]]
Output:
2
Note:
U1, U2, U3 are connected (U1-U2, U2-U3). U4, U5, U6 are connected (U4-U5, U6-U4). This results in two distinct clusters.
Example 3
Input:
accounts = ["P1", "P2", "P3"], linkages = []
Output:
3
Note:
With no linkages, each account forms its own cluster. Total 3 distinct clusters.
Constraints
1 <= accounts.length <= 10^50 <= linkages.length <= 2 * 10^51 <= account_id.length <= 10 for all account IDs.account_ids in the accounts array are unique.linkages is undirected.linkages (assume all are valid).account_id string lengths.Loading editor...