TopCoder problem "TrafficMonitor" used in TCO06 Wildcard (Division I Level One)

Problem Statement

You are given a network where each pair of nodes is connected by at most 1 path. Your boss has told you to place traffic monitors on certain nodes to better supervise the network. A single monitor can watch all links directly connected to the node it is attached to. Assuming every link must be watched, return the fewest number of monitors that must be installed.

Nodes i and j share a symmetric link in your network if character j of element i of links is 'Y' ('N' otherwise). A path is a sequence of distinct nodes such that neighbors in the sequence share a link.

Definition

Class:	TrafficMonitor
Method:	getMin
Parameters:	String[]
Returns:	int
Method signature:	int getMin(String[] links)
(be sure your method is public)

Constraints

links will contain between 1 and 50 elements, inclusive.

Each element of links will contain exactly N characters, where N is the number of elements in links.

Each character of links will be 'Y' or 'N'.

Character i of element i of links will be 'N'.

Character i of element j of links will equal character j of element i.

There will be at most one path between any two nodes.

Examples

{
"NN",
"NN"
}

Returns: 0

There are no edges to monitor.

{
"NYNN",
"YNYN",
"NYNY",
"NNYN"
}

Returns: 2

{
"NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNYNNNNNNN",
"NNNNNNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
"NNNNNNNNNNNNNNYNNNNNYNNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNN",
"YNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNN",
"NYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNN",
"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNYNNYNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNYNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN",
"NNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNYNNN",
"NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNN",
"NNNNNNNNYYNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNYNNNNNNNNNNNNNNNNNNNNNNYNNNNYNNNNNYNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYN",
"NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNY",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNN",
"NNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNYNNNN",
"NNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYNNN",
"NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNYNNNNNN",
"NNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNYNNNNNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNY",
"NNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNYNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNN",
"NNNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNYNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNYNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNNNNNNNN"
}

Returns: 22

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9983&pm=6165

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , vorthys , Olexiy

Problem categories:

Graph Theory