G - Telecommunication Partners
Languages: C, C++, Java, JavaScript, Haskell, Tiger, Python, Pascal, C#
Time & Memory limits:
(details)
ICPC, an international telecommunication company, wants to improve its relationship with business subscribers, offering a discount on calls made to a fixed set of telephone numbers selected by the client company. To help ICPC decide on the cost for this new service, they searched their database and produced a list of calls made last year by one company to another. If a company communicated with another company (making or receiving a call) during last year, we will say they are Business Partners.
You have been hired by ICPC to process the list of calls from last year and determine the size (in number of companies) of the largest set of companies that are Business Partners of at least $K$ other companies in the same set. That is, you must find a set S of companies such that every company in $S$ has at least $K$ business partners that are also in $S$ (and possibly partners that are outside $S$), where $K$ is a parameter chosen by the ICPC.
Output
For each test case from the input, your program should print a single line, containing the size of the largest set of companies found by your program.