TopCoder problem "RoadReform" used in East China Round 2 (Division I Level Three)



Problem Statement

    

There are n cities in the Kingdom. Some pairs of cities are connected by bidirectional roads, and there exists a path between every pair of cities.

The King thinks that supporting so many roads is very expensive, so he decided to close some of them. He wants to close as many roads as possible, but, of course, he still wants each city to be reachable from any other city.

A city is a dead end if it is connected to only one other city by a direct road. You will be given a String[] roads, with the j-th character of the i-th element of roads being '1' (one) if the i-th and j-th cities are connected by a direct road, and '0' (zero) otherwise. Return the maximal number of dead ends the Kingdom may have after the reform.

 

Definition

    
Class:RoadReform
Method:findMaxDeadendCount
Parameters:String[]
Returns:int
Method signature:int findMaxDeadendCount(String[] roads)
(be sure your method is public)
    
 

Constraints

-roads will contain between 2 and 15 elements, inclusive.
-Each element of roads will contain exactly n characters, where n is the number of elements in roads.
-Each element of roads will contain digits '0' and '1' only.
-The j-th character in the i-th element of roads will be equal to the i-th character in the j-th element.
-The i-th character in the i-th element of roads will be '0'.
-Each pair of cities in the input will be connected by a path.
 

Examples

0)
    
{"01",
 "10"}
Returns: 2
Two cities are connected by a road. The King can't close this road and both cities will still be dead ends.
1)
    
{"01000", 
 "10100",
 "01010",
 "00101",
 "00010"}
Returns: 2
The cities of the Kingdom are aligned in a chain. As in example 0, no road can be closed without splitting the Kingdom.
2)
    
{"01111",
 "10000",
 "10000",
 "10000",
 "10000"}
Returns: 4
3)
    
{"0111",
 "1011",
 "1101",
 "1110"}
Returns: 3
Each pair of cities is connected by a direct road. The King can close roads 1<->2, 2<->3 and 1<->3, thus making cities 1, 2 and 3 dead ends.
4)
    
{"0100000001",
 "1010000000",
 "0101000000",
 "0010100000",
 "0001010000",
 "0000101000",
 "0000010100",
 "0000001010",
 "0000000101",
 "1000000010"}
Returns: 2

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9721

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12227&pm=9721

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Graph Theory