Host Community Connectivity
Airbnb thrives on fostering connections, not just between guests and homes, but also among its hosts. To support initiatives like local host meetups, shared resource programs, or identifying regional host leaders, it's crucial to efficiently determine if hosts belong to the same 'community' based on various shared criteria. This problem challenges you to design a system that can manage host relationships and quickly answer queries about community membership.
Your task is to implement a HostCommunityManager class that efficiently handles host relationships and community queries.
HostCommunityManager(numHosts). This should initialize the system for numHosts hosts, indexed from 0 to numHosts - 1. Initially, each host is in their own distinct community.establishRelationship(hostA, hostB). This method should merge the communities of hostA and hostB, indicating they are now part of the same collective.areInSameCommunity(hostA, hostB). This method should return true if hostA and hostB currently belong to the same community, and false otherwise.HostCommunityManager(numHosts: number)numHosts: An integer representing the total number of hosts to manage. Hosts are identified by 0-indexed integers from 0 to numHosts - 1.void (constructor).establishRelationship(hostA: number, hostB: number): voidhostA, hostB: Integers representing the IDs of two hosts whose communities should be merged.void.areInSameCommunity(hostA: number, hostB: number): booleanhostA, hostB: Integers representing the IDs of two hosts to check for community membership.true if hostA and hostB are in the same community; false otherwise.establishRelationship with hosts already in the same community should not cause errors and should result in no change to the community structure.Examples
Example 1
Input:
operations = ["HostCommunityManager","establishRelationship","establishRelationship","areInSameCommunity","areInSameCommunity","establishRelationship","areInSameCommunity"], params = [[4],[0,1],[2,3],[0,1],[0,2],[0,2],[1,3]]
Output:
[null,null,null,true,false,null,true]
Note:
establishRelationship(0, 1): Communities are now {0,1}, {2}, {3}establishRelationship(2, 3): Communities are now {0,1}, {2,3}areInSameCommunity(0, 1): Returns true (0 and 1 are connected)areInSameCommunity(0, 2): Returns false (0 is not connected to 2)establishRelationship(0, 2): Communities are now {0,1,2,3} (0's community merges with 2's)areInSameCommunity(1, 3): Returns true (1 and 3 are now connected via 0 and 2)Example 2
Input:
operations = ["HostCommunityManager","establishRelationship","areInSameCommunity","establishRelationship","areInSameCommunity","areInSameCommunity"], params = [[3],[0,1],[0,1],[1,1],[0,2],[1,2]]
Output:
[null,null,true,null,false,false]
Note:
establishRelationship(0, 1): Communities are now {0,1}, {2}areInSameCommunity(0, 1): Returns trueestablishRelationship(1, 1): No change, 1 is already in its own community. Communities remain {0,1}, {2}areInSameCommunity(0, 2): Returns falseareInSameCommunity(1, 2): Returns falseExample 3
Input:
operations = ["HostCommunityManager","establishRelationship","establishRelationship","establishRelationship","areInSameCommunity"], params = [[5],[0,1],[1,2],[3,4],[0,4]]
Output:
[null,null,null,null,false]
Note:
establishRelationship(0, 1): {0,1}, {2}, {3}, {4}establishRelationship(1, 2): {0,1,2}, {3}, {4}establishRelationship(3, 4): {0,1,2}, {3,4}areInSameCommunity(0, 4): Returns false (0 and 4 are in different communities)Constraints
1 <= numHosts <= 10^50 <= hostA, hostB < numHostsestablishRelationship and areInSameCommunity combined will not exceed 2 * 10^5.hostA, hostB) will be valid within the 0 to numHosts - 1 range.find, union) are implemented without logical errors.establishRelationship and areInSameCommunity operations achieve near-constant time complexity (amortized O(α(N))) through optimizations like path compression and union by size/rank.Loading editor...