TopCoder problem "TeamBuilding" used in SRM 184 (Division I Level Three)



Problem Statement

    You are arranging a weird game for a team building exercise. In this game there are certain locations that people can stand at, and from each location there are paths that lead to other locations, but there are not necessarily paths that lead directly back. You want the paths set up such that regardless of where someone starts, there will be at least one path they can take that will return to their starting location. You already have the locations set up, and some paths connecting them. You want to know the fewest paths that you have to add such that everything is set up the way you need it.



Create a class TeamBuilding with a method fewestPaths that takes a String[] paths that describes the way the locations are currently connected, and returns an int that is the fewest number of paths that must be added. Each element of paths will be a String containing as many characters as there are elements in paths. The i-th element of paths (beginning with the 0-th element) will contain a '1' (all quotes are for clarity only) in position j if there is a path that leads directly from i to j, and a '0' if there is not a path that leads directly from i to j.
 

Definition

    
Class:TeamBuilding
Method:fewestPaths
Parameters:String[]
Returns:int
Method signature:int fewestPaths(String[] paths)
(be sure your method is public)
    
 

Notes

-There may be paths that leads directly from one location to that same location.
 

Constraints

-paths will contain between 2 and 20 elements, inclusive.
-Each element of paths will contain only the characters '0' and '1'.
-Each element of paths will contain as many characters as there are elements in paths.
 

Examples

0)
    
{"010",
 "100",
 "000"}
Returns: 1
There are paths leaading from location 0 to location 1, and from location 1 to location 0. By adding a path from location 2 to itself, all locations will be able to follow a set of paths that lead back to themselves.
1)
    
{"0110",
 "0001",
 "0101",
 "1000"}
Returns: 0
There already exists a set of paths for each location that leads back to itself.
2)
    
{"00101",
 "00010",
 "00010",
 "10000",
 "00000"}
Returns: 1
3)
    
{"001000000",
 "000000010",
 "000001000",
 "000010010",
 "000000000",
 "000000010",
 "000000000",
 "100000001",
 "010000100"}
Returns: 2

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4740&pm=2327

Writer:

Running Wild

Testers:

lbackstrom , brett1479

Problem categories:

Graph Theory