TikTok OA 面试真题解析：Adding Connections 图论并查集

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.

这道题本质上是图论里的“在约束下尽量补边”问题：把所有未验证用户视为特殊点，要求它们之间不能通过任何路径间接连通，因此不能随意把不同连通块合并。通常做法是先用并查集或 DFS/BFS 求出原图的连通分量，再区分哪些分量包含 unverified 用户、哪些分量完全由 verified 用户组成。关键贪心点在于：verified 分量之间通常可以尽量合并并补成更稠密的结构，而每个包含 unverified 的分量只能与允许的目标分量连接，且要保证所有 unverified 彼此仍然隔离。最终答案就是在满足这些约束下，统计还能加入的边数。