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.