PROBLEM LINKS:
DIFFICULTY
HARD
EXPLANATION
Let’s focus on finding the number of vertices and edges of G2 first. According to the problem statement, each vertex of G1 corresponds to an edge of G0, and each edge of corresponds to a pair of edges of sharing a common vertex. That means that each vertex of G2 corresponds to a pair of edges of G0 sharing a common vertex as well, and a bit of thinking on paper leads to a conclusion that each edge of G2 corresponds to two pairs of edges of G0 (each pair sharing a common vertex in G0) sharing a common edge.
Both numbers can be calculated in a fairly easy way now. For the number of vertices of G2, let’s consider each vertex of G0 as the shared vertex between two edges. Suppose this vertex has degree (the number of outgoing edges) equal to D. Then it’s easy to see that there are D *(D-1)/2 pairs of edges sharing this particular vertex. For the number of edges of G2, let’s consider each edge of G0 as the shared edge between two pairs of edges. Suppose the total degree of this edge’s ends is equal to D. Then, again, there are D * (D-1)/2 pairs of pairs of edges sharing this particular edge. As the degrees of all vertices can be easily calculated in O(M) time, the number of vertices and edges in G2 can be calculated in the same time.
The last thing to notice is that graph G1 is not really big. It has at most 1000 vertices, and in the worst case it has 1000 * 999/2 = 499500 edges, so it’s enough to write down G1 explicitly and then use the aforementioned algorithm to find the number of vertices and edges in G3, as required.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.