TopCoder problem "Provinces" used in TCHS07 Gamma 3 (Division I Level Three)



Problem Statement

    

In one country there are n cities numbered from 1 to n. Some of them are connected by one-way roads. There are n-1 main roads: for all i from 1 to n-1 there is a road from i to i+1, and there are also some auxiliary roads.

The king of the country decided to divide it into provinces. He wants to create as many provinces as possible. All provinces must contain the same number of cities. Each city must belong to exactly one province. For each pair of distinct provinces A and B, the following condition must be satisfied. If there is a path from some city in A to some city in B, there must be no paths that go from province B to province A.

You are given a int n and a String[] roads containing all the auxiliary roads in the country. First, concatenate all the elements of roads. The resulting String is a comma-separated list of integer pairs. Each pair is formatted as "i j" (quotes for clarity), which means there's an auxiliary road from i to j. Return the maximum possible number of provinces that can be created.

 

Definition

    
Class:Provinces
Method:maximalNumber
Parameters:int, String[]
Returns:int
Method signature:int maximalNumber(int n, String[] roads)
(be sure your method is public)
    
 

Constraints

-n will be between 2 and 3000, inclusive.
-roads will contain between 0 and 50 elements, inclusive.
-Each element of roads will contain between 1 and 50 characters, inclusive.
-roads will be formatted as described in the problem statement.
-In each integer pair "i j" in roads, i and j will be distinct integers between 1 and n, inclusive, with no leading zeroes, and j will not be equal to i+1.
-All integer pairs in roads will be distinct.
 

Examples

0)
    
6
{"2 1,3 2,6 4"}
Returns: 2
Two provinces can be created: {1, 2, 3} and {4, 5, 6}.
1)
    
3
{}
Returns: 3
It is possible to make three provinces, a separate province for each city.
2)
    
3
{"1 3"}
Returns: 3
It is also possible to create three provinces.
3)
    
3
{"2 1"}
Returns: 1
In this case all cities must belong to the same province.
4)
    
12
{"3 1,", "7 6,", "1 1", "0"}
Returns: 3
Note that you must concatenate elements of roads before parsing, in this case you get String "3 1,7 6,1 10".

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10720&pm=7496

Writer:

andrewzta

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Search, String Parsing