FastPrep

Description

Solutions

Hotspot Connections

🔥 FULLTIME📚RELATED PROBLEMS

There are employee_nodes employees in a company, out of which there are k special employees who have data network and share their mobile hotspots with other employees. There are employee_edges connections already made between the employees, where the i^th connection connects the employees employee_from[i] and employee_to[i], such that either of the employees employee_from[i] and employee_to[i] can share a mobile hotspot.

Two employees x and y are connected if there is a path between them. All the employees connected to a special employee x will use the mobile hotspot of the special employee x.

Up to now, to restrict data usage, any employee was connected to at most one special employee. As data consumption has increased, any employee can be connected to at most max_connections number of special employees.

Find the maximum number of edges that can be added to the graph such that any employee is connected to at most max_connections special employees.

Note:

The given graph does not contain self-loops or multiple edges between nodes. The graph formed after adding edges should not contain self-loops or multiple edges.
It is guaranteed that in the given graph, no two special employees are connected to each other.

Function Description

Complete the function getMaximumEdges in the editor.

getMaximumEdges has the following parameters:

int employee_nodes: the number of employees
int employee_from[employee_edges]: the one end of the connection
int employee_to[employee_edges]: the other end of the connection
int special_employees[k]: the special employees
int max_connections: the maximum number of special employees to which an employee can be connected

Returns

long: the maximum number of edges that can be added to the graph such that any employee is connected to at most max_connections number of special employees

Example 1:

Input:  employee_nodes = 4, employee_from = [1], employee_to = [2], special_employees = [1, 3], max_connections = 1
Output: 2 
Explanation:
      
      It is given that employee_nodes = 4, employee_edges = 1, k = 2, max_connections = 1, special_employees = [1, 3], employee_from = [1], and employee_to = [2].
      
      
      Disjoint graph with 4 nodes numbered 1 to 4. Node 1 and 2 are connected through a bidirectional edge.
      
      
      Employees 1 and 3 are special, and max_connections = 1, so they cannot be connected. Hence, employee 4 can be connected to 1 and 2, making two total edges.
      
      
      Hence, the answer is 2.

Example 2:

Input:  employee_nodes = 5, employee_from = [1, 2, 1], employee_to = [2, 3, 3], special_employees = [1, 4, 5], max_connections = 3
Output: 7 
Explanation:
      
      As max_connections = k = 3, hence we can connect all the employees, thus forming a fully connected graph.
      
      
      Hence, the answer is 7.

Constraints:

1 ≤ employee_nodes ≤ 2 * 10^5
0 ≤ employee_edges ≤ min(2 * 10^5, employee_nodes * (employee_nodes - 1) / 2)
1 ≤ max_connections ≤ k ≤ employee_nodes
1 ≤ employee_from[i], employee_to[i] ≤ employee_nodes
1 ≤ special_employees[i] ≤ employee_nodes