Clusters

SRM 135 · 2003-02-11 · by axchma

Class Name: Clusters

Return Type: String[]

Method Name: mostClustered

Arg Types: (vector<string>)

Problem Statement

The World Wide Web (WWW), as we all know, is a collection of pages, which are linked together to form a very large graph, where each page represents a node in the graph, and each link represents a directed edge. Since there are billions of pages on the WWW, it is important to be able to search through them, and have good methods to determine which ones are relevant.

One statistic about a page that might be of interest to a search engine is its clustering coefficient. To find the clustering coefficient of a page, p, first we find all of the pages that p links directly to. Then, we count the total number of links between all of those pages and divide by the total number of possible links between those pages (for our purposes, a pages may not be linked multiple times to the same page). If p links to zero or one pages, then its clustering coefficient is undefined. Note that clustering coefficients are usually used in conjunction with undirected graphs, but that we are expanding them here to be used on directed graphs (since the links in the WWW are directed).

Your task is, given a list of pages, and how they are linked together, determine the pages with the maximal (defined) clustering coefficient. You will be given a String[], links, where each element is a single-space delimited list of the names of the pages. The first term represents the page that the links are on, and the remaining terms represent the pages that it links to. So, "A B C D" would mean that page "A" has a link to pages "B", "C", and "D". You are to return a String[] that contains all of the pages which have the maximal clustering coefficient sorted in lexicographic order. If all of the pages have an undefined clustering coefficient, return an empty String[].

Notes

Assume that the same name always describes the same page.

Constraints

links has between 1 and 20 elements inclusive
each element of links will contain between 1 and 50 characters inclusive.
each element of links consists only of upper-case letters ('A'-'Z') and spaces
each element of links doesn't contain leading/trailing spaces
each element of links consists of single-space delimited names
no element of links contains duplicate name
no two elements of links start with the same name
no page links to itself

Examples

{"A B C D", "B A E D"}
Returns: { "A",  "B" }

"A" is linked to three pages, "B", "C", and "D". There are 6 different possible links between these three pages (B->C, B->D, C->B, C->D, D->B, D->C). Only one of these links (B->D) actually exists, so the clustering coefficient of "A" is 1/6. "B" is also linked to three pages, which have 6 possible links between them. Only one of the possible links exists though (A->D) so its clustering coefficient is also 1/6. All of the other pages have undefined clustering coefficients, since they do not link to any pages. Thus, both "A" and "B" have the maximal clustering coefficient of 1/6, and we return then in sorted order.

{"A", "B"}
Returns: { }

A and B are not linked to any other pages.

{"A B C D", "B A C D", "C D A B", "D A B C"}
Returns: { "A",  "B",  "C",  "D" }

{"A B C D", "B A C", "C D A B", "D A C"}
Returns: { "B",  "D" }

{"A B C D", "B A C", "C A B", "D B C"}
Returns: { "B",  "C",  "D" }

{"A B C D E F",
"B A C D E F",
"C A B D E F",
"D A B C E F",
"E A B C D F",
"F A B C D E"}
Returns: { "A",  "B",  "C",  "D",  "E",  "F" }

Every page links to every other page here.

Submissions are judged against all 45 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Clusters with a public method vector<string> mostClustered(vector<string> links) · 45 test cases · 2 s / 256 MB per case