Monitored Merchant Clusters
Razorpay processes a vast number of transactions daily, involving a complex network of merchants. To maintain financial stability and detect potential anomalies, it's crucial to monitor how merchants form operational clusters through 'trust' relationships. Some merchants are flagged as 'high-risk' based on various criteria. We need to ensure that as new trust relationships are established, the resulting merchant clusters remain stable, meaning the proportion of high-risk merchants does not exceed a predefined threshold.
Implement a function countStableClusters that, given an initial set of merchants (some marked as high-risk) and a series of potential trust relationships, determines the final number of stable merchant clusters.
Your solution should:
trustRelationship sequentially.(u, v):
u and v are already in the same cluster, do nothing.k, then u and v's clusters should be merged.k, the trust relationship is deemed unstable and the clusters remain separate.Function Signature:
function countStableClusters(n: number, highRiskMerchants: number[], trustRelationships: number[][], k: number): number
n: An integer representing the total number of merchants, indexed from 0 to n-1.highRiskMerchants: An array of integers, where each integer is the 0-based index of a merchant identified as high-risk.trustRelationships: An array of [u, v] pairs. Each pair represents a potential trust relationship between merchant u and merchant v.k: A floating-point number representing the maximum allowed ratio of high-risk merchants to total merchants within any stable cluster. A ratio R is stable if R <= k.k can be 0.0 (no high-risk merchants allowed in any cluster) or 1.0 (any number of high-risk merchants allowed).n >= 1) would have an undefined ratio. A cluster with 0 high-risk merchants and any positive total count has a ratio of 0.a / b <= k comparison is generally acceptable for typical competitive programming scenarios unless extreme precision is specified. For strictness, consider a <= k * b to avoid floating-point division issues, especially if b can be 0 (though b will be at least 1 here).Examples
Example 1
Input:
n = 5, highRiskMerchants = [0, 2], trustRelationships = [[0, 1], [3, 4]], k = 0.5
Output:
3
Note:
Initial: 5 clusters. High-risk merchants: {0, 2}.
Example 2
Input:
n = 4, highRiskMerchants = [0, 1], trustRelationships = [[0, 2], [1, 3], [2, 3]], k = 0.3
Output:
3
Note:
Initial: 4 clusters. High-risk merchants: {0, 1}.
Example 3
Input:
n = 6, highRiskMerchants = [0, 1, 3], trustRelationships = [[0, 2], [1, 4], [2, 5], [3, 5]], k = 0.4
Output:
4
Note:
Initial: 6 clusters. High-risk merchants: {0, 1, 3}.
Constraints
1 <= n <= 10^50 <= highRiskMerchants.length <= n0 <= trustRelationships.length <= 2 * 10^50.0 <= k <= 1.0u, v in trustRelationships are distinct merchant indices, 0 <= u, v < n.u != v for all relationships.[u, v] is the same as [v, u].k is maintained.Loading editor...