Problem Statement |
| | You are given an electrical circuit for a home, with a number of nodes possibly connected by wires. Any pair of nodes may be connected by at most one wire, and a node can't be connected to itself. Each node on the circuit is either an electrical outlet for the house or a connection to the main electrical grid. The String[] wires tells you the wires that are already in place; the xth character of the yth element is '1' (one) if nodes x and y have a wire between them, '0' (zero) otherwise. The int[] gridConnections lists the indices of the nodes that are connections to the main electrical grid.
You'd like to make the circuit safer and more redundant by adding as many extra wires to it as possible. The one complication is that no two main grid connections are currently wired together (directly or indirectly), and you must preserve this, or else disaster will result. Determine the maximum number of new wires you can add to the circuit. |
| |
Definition |
| | | Class: | AddElectricalWires | | Method: | maxNewWires | | Parameters: | String[], int[] | | Returns: | int | | Method signature: | int maxNewWires(String[] wires, int[] gridConnections) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | wires will contain between 1 and 50 elements, inclusive. |
| - | Each element of wires will have the same length as wires. |
| - | Each element of wires will contain only the characters '0' and '1'. |
| - | Character i of element i of wires will be a '0'. |
| - | Character i of element j of wires will be the same as character j of element i. |
| - | gridConnections will contain between 1 and 50 elements, inclusive. |
| - | Each element of gridConnections will be an integer between 0 and length(wires)-1, inclusive. |
| - | Each element of gridConnections will be distinct. |
| - | Each pair of elements of gridConnections will not index nodes connected by a path of '1's in wires. |
| |
Examples |
| 0) | |
| | | Returns: 3 | | Every valid wire can be added. |
|
|
| 1) | |
| | | Returns: 1 | | 0 and 1 can't be connected, but 0 and 2 (or 1 and 2) still can be. |
|
|
| 2) | |
| | | Returns: 0 | | This circuit is already complete. |
|
|
| 3) | |
| | {"00000","00000","00000","00000","00000"} | {0,1,2,3,4} |
| Returns: 0 | | Any connections would be disastrous. |
|
|
| 4) | |
| | {"01000","10100","01010","00100","00000"} | {2,4} |
| Returns: 3 | |
|