Consolidate User Communities
In a large social platform, users can be part of many different groups. Over time, groups might become highly interconnected through shared users. To streamline communication and management, we need a way to identify and consolidate all groups that are effectively part of a larger "super-group" due to shared members. This problem focuses on efficiently determining the total number of distinct, consolidated user communities.
You are given a list of user groups, where each groups[i] represents a distinct group and contains a list of user IDs belonging to that group. Your task is to implement a function that returns the total number of distinct, consolidated communities. Two groups are considered part of the same community if they share at least one common user, or if they are transitively linked through other groups that share common users.
The function countConsolidatedCommunities takes one argument:
groups: An array of arrays of numbers. groups[i] is a list of unique user IDs belonging to the i-th group.The function should return:
groups array implies 0 communities.groups[i] means that group has no users and cannot connect to any other group through users.Examples
Example 1
Input:
groups = [[1,2], [2,3], [4,5]]
Output:
2
Note:
Groups [1,2] and [2,3] share user 2, forming one community. Group [4,5] forms a separate community. Total 2 communities.
Example 2
Input:
groups = [[10,20], [30,40], [10,30], [50]]
Output:
2
Note:
Groups [10,20], [30,40], and [10,30] are all interconnected (10 links first and third, 30 links second and third). They form one large community. Group [50] forms a separate community. Total 2 communities.
Example 3
Input:
groups = [[1], [2], [3]]
Output:
3
Note:
No groups share users. Each group forms its own community. Total 3 communities.
Constraints
0 <= groups.length <= 10000 <= groups[i].length <= 10001 <= user_id <= 10^9 for any user ID.user_id within a single groups[i] is unique.Loading editor...