Merging Communities

The 'Network Connectivity' problem focuses on modeling a social network where individuals can form connections, merging their friend groups. This tests your ability to efficiently track group memberships and sizes after a series of connection events, a common pattern in graph algorithms and data structure optimization.

graphdisjoint set unionunion-finddata structuresconnectivity

Problem Statement

Imagine you're building a social networking platform where users can connect with each other. Initially, every user is in their own isolated network. When two users connect, their networks merge into a single, larger network. You need to implement two functionalities: first, a connect(user1, user2) function that merges the networks of two users; and second, a get_network_size(user) function that returns the number of users in the network to which a given user belongs.

Example 1

Input: n = 6, [connect(0, 2), connect(1, 3), get_network_size(0), connect(2, 4), get_network_size(1), get_network_size(5)]

Output: [1, 2, 1]

Initially, each of the 6 users is in their own network of size 1. After connecting users 0 and 2, the network containing user 0 has size 1 (only user 0 is checked). After connecting users 1 and 3, the network containing user 1 has size 1. After connecting users 2 and 4, the network containing user 5 has size 1.

Example 2

Input: n = 7, [connect(0, 1), connect(2, 3), connect(1, 2), get_network_size(0), get_network_size(4), connect(4, 5), connect(5, 6), get_network_size(6)]

Output: [3, 1, 3]

Initially, each of the 7 users is in their own network of size 1. After connecting 0 and 1, and then 2 and 3, and finally 1 and 2, the networks {0, 1, 2, 3} merge. So, get_network_size(0) returns 3 (users 0, 1, 2 are connected). User 4 is in its own network of size 1. After connecting 4, 5 and 5, 6, users 4, 5, and 6 are connected in a network of size 3. Therefore, get_network_size(6) returns 3.

Constraints

-1 <= n <= 10^5 (Number of users)
-0 <= user1, user2 < n
-user1 != user2 in connect operations
-The connect and get_network_size operations can be called in any order.
-The number of connect and get_network_size operations will be at most 10^5.

Brute Force Approach

The brute-force approach would involve, for each connect operation, traversing the entire network to update the network memberships of all users. Think of it like manually re-drawing lines between friends on a whiteboard every time two people become friends. Each get_network_size operation would also require traversing the network. This is inefficient because it involves repeatedly revisiting the same connections.

TimeO(n*m)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem