TopCoder problem "FriendsTrouble" used in TCHS SRM 14 (Division I Level Two)



Problem Statement

    

You are given a list of people, and you must divide them into as many groups as possible. Each person must belong to exactly one group, and each group must contain one or more people. Friends must not be split apart, so if two people are friends, they must be in the same group.

You will be given a String[] names, each element of which is the name of a single person. You will also be given a String[] friends, each element of which is formatted as "<name1> <name2>" (quotes for clarity only), meaning that <name1> and <name2> are friends. Each <name1> and <name2> will exist in names. Return the maximum number of groups that can be formed.

 

Definition

    
Class:FriendsTrouble
Method:divide
Parameters:String[], String[]
Returns:int
Method signature:int divide(String[] names, String[] friends)
(be sure your method is public)
    
 

Constraints

-names will contain between 1 and 50 elements, inclusive.
-Each element of names will contain between 1 and 20 uppercase letters ('A'-'Z'), inclusive.
-All elements in names will be distinct.
-friends will contain between 0 and 50 elements, inclusive.
-Each element of friends will be formatted as "<name1> <name2>" (quotes for clarity only), where both <name1> and <name2> are elements of names.
 

Examples

0)
    
{"BOB", "HARRY", "ALICE", "SALLY"}
{"BOB ALICE", "HARRY SALLY"}
Returns: 2
BOB and ALICE form one group, and HARRY and SALLY form a second group. The only other valid division is putting them all in a single group, but we want to maximize the number of groups
1)
    
{"BOB", "HARRY", "ALICE", "SALLY"}
{"BOB HARRY", "HARRY ALICE", "ALICE SALLY" }
Returns: 1
There is no way to form more than one group without separating a pair of friends.
2)
    
{"CHUCK"}
{"CHUCK CHUCK","CHUCK CHUCK","CHUCK CHUCK"}
Returns: 1
CHUCK is his own only friend. Note that friends may have duplicate entries.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10066&pm=6721

Writer:

slex

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Graph Theory