Bob recently completed his Computer Science degree and applied for an internship in Doogle – the biggest IT company in the universe of Algoria. The interviewer gave him the following task:
Imagine a weighted graph with 5 000 000 vertices and 5 000 000 edges. Let's assume that the edges are somehow ordered, and their weights are as follows: the first edge has a weight equal to one, the second edge has a weight , and so on, the last edge weighing . Your task is to compute the number of minimum spanning trees in the given graph.
Bob was an attentive learner, hence he answered correctly. What should be the answer to this challenging task?