ZOJ Problem Set - 3909
Gene clusters are common features of plants. Most clustered genes known are involved in the biosynthesis of secondary metabolites.The indentification of gene cluster means a lot for scientific research.Lets do this interesting work.
To clarify this problem,two tips following:
The gene cluster which contains the biggest number of genes is called the biggest gene cluster.Given a set of genes with their type and coexpression information,please tell us how many genes are involved in the biggest gene cluster.
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
For each case,print the number of genes in the biggest gene cluster.If the given genes can’t form any cluster,print “None”.
2 4 2 S0001 S0002 S0002 S0003 S0003 S0004 S0007 S0009 S0002 S0004 2 1 S1001 S1003 S1002 S1003 S1001
Case 1: The biggest cluster is S0001,S0002,S0003 and the answer is 3. S0002 is special and coexpresses with two genes(S0001 and S0003),so it can be added. S0004 is special but coexpresses with only one gene(S0003),so it can’t be added.
Case 2:Two genes can not form a cluster.
You could just image genes are cities and coexpression are roads,In the choosen group,all cities are combined by roads,special city has at least two direct ways to other two cities in group,common city has at least one direct way to another city in group,the question is that if a group has most cities(if the number is less than 3,it can't be called a group),print the number of cities in the group.
Author: ZHANG, Xingchen
Source: ZOJ Monthly, October 2015