TikTok OA Interview Question: Adding Connections Graph / Union-Find

6. Adding Connections

In a TikTok-like social media platform, users are either verified or unverified. Unverified users cannot interact with each other in any way — neither directly nor indirectly. This means that even if there is a chain of interactions connecting unverified users through verified users, such connections must be avoided.

You are given a graphical representation of the platform. There are a total of user_nodes users. Their existing interactions are given in the form of two arrays, user_from and user_to, both of size m. This means that there is a connection between user_from[i] and user_to[i] for all 1 <= i <= m.

You are also given an array of unverified users, unverified. Find the maximum number of new connections that can be added while ensuring that unverified users remain isolated from each other.

Note:

• The connections are bidirectional. If user A has a connection to user B, user B also has a connection to user A.
• A user cannot have a connection to itself.
• There can be at most one connection between a given pair of users.

Function Description

Complete the function maxNewConnections in the editor below.

• int user_nodes: the number of users
• int user_from[m]: the users at one end of each connection
• int user_to[m]: the users at the other end of each connection
• int unverified[k]: the users that are unverified

Returns

int: the maximum number of edges that can be added to the graph

Constraints

1 <= user_nodes <= 10^5
0 <= m <= 10^5
0 <= k <= 10^5
1 <= user_from[i], user_to[i], unverified[j] <= n
It is guaranteed that the graph does not have any two path connecting unverified users directly or indirectly.

Sample Case 0

Sample Input For Custom Testing

6 4
1 2
1 3
2 3
4 5
2
2 4

Sample Output

3

Explanation

3 new connections can be made. User 6 can be connected to Users 1, 2, and 3.

This is a graph optimization problem with a separation constraint on unverified users. The usual approach is to compute connected components with DFS/BFS or union-find, classify components that contain unverified nodes, and then greedily add edges only where they do not create a path between any two unverified users. The core challenge is balancing component merging and edge counting while preserving isolation among the special nodes.