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 vector 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 vector 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:vector , vector
Returns:int
Method signature:int maxNewWires(vector wires, vector gridConnections)
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)
{"000","000","000"}
{0}
Returns: 3
Every valid wire can be added.
1)
{"000","000","000"}
{0,1}
Returns: 1
0 and 1 can't be connected, but 0 and 2 (or 1 and 2) still can be.
2)
{"01","10"}
{0}
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
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.