339. Maximum Added Edges in an Network With Special Employees

Maximum Added Edges in an Network With Special Employees

A company has employeeNodes employees numbered from 1 to employeeNodes. Some employees are special employees who can share their mobile hotspots through the company's network.

The existing network contains undirected connections. The connection at index i joins employeeFrom.get(i) and employeeTo.get(i). Two employees are connected when a path exists between them.

Every employee may belong to a connected component containing at most maxConnections special employees. Return the maximum number of new connections that can be added without violating this limit.

Class Definition

EmployeeNetwork()

Method Signature

long getMaximumEdges(int employeeNodes, List<Integer> employeeFrom, List<Integer> employeeTo, List<Integer> specialEmployees, int maxConnections)

employeeNodes is the total number of employees.
employeeFrom and employeeTo describe the endpoints of the existing undirected connections.
specialEmployees contains the distinct special employee numbers.
maxConnections is the maximum number of special employees permitted in any connected component.
Returns the maximum number of connections that can be added.

Connection Rules

Connections are undirected.
An employee cannot be connected directly to itself.
Multiple direct connections between the same two employees are not allowed.
After adding connections, every connected component must contain at most maxConnections special employees.
In the initial network, no two special employees are connected by a path.
Existing connections cannot be removed.

Constraints

1 ≤ employeeNodes ≤ 200,000
0 ≤ employeeFrom.size() ≤ 200,000
employeeFrom.size() = employeeTo.size()
1 ≤ specialEmployees.size() ≤ employeeNodes
1 ≤ maxConnections ≤ specialEmployees.size()
1 ≤ employeeFrom.get(i), employeeTo.get(i) ≤ employeeNodes
employeeFrom.get(i) != employeeTo.get(i)
Every value in specialEmployees is between 1 and employeeNodes.
The initial network contains no self-loops or duplicate connections.

Examples

Example 1

getMaximumEdges(employeeNodes = 6, employeeFrom = [1, 4], employeeTo = [2, 5], specialEmployees = [1, 4], maxConnections = 1)

Output: 5

The components containing special employees 1 and 4 cannot be joined. Employees 3 and 6 can be added to one of those components, allowing five new connections in total.

Example 2

getMaximumEdges(employeeNodes = 7, employeeFrom = [1, 3, 5], employeeTo = [2, 4, 6], specialEmployees = [1, 3, 5], maxConnections = 2)

Output: 8

Two special-employee components may be joined because the limit is 2. Employee 7 can also join the resulting component, and all permitted missing connections can then be added.

Example 3

getMaximumEdges(employeeNodes = 5, employeeFrom = [1, 3], employeeTo = [2, 4], specialEmployees = [1, 3], maxConnections = 2)

Output: 8

Since both special employees may belong to the same component, all five employees can be fully connected. A complete network has ten connections, and two connections already exist, so eight can be added.