Problem link: Contest
PROBLEM:
Given an unweighted undirected graph, an edge u-v is called interesting iff for all other vertices w, w is connected to either u or v (or maybe both). Find the number of interesting edges.
TL;DR:
At least one of the vertices in any interesting edge must have degree \geq n/2 where n is the total number of vertices, and the number of such vertices is pretty small.
FULL SOLUTION:
Let’s see how to find the number of interesting edges passing through a fixed vertex v in O(m+n). Make an array cnt[1 … n] where cnt[i]=0 for all i initially. For each vertex u≠v which is not a neighbor of v, add 1 to cnt[w] for all w that is a neighbor of u. After this is done, cnt[i] will store the number of non-neighbors of v adjacent to i. Now note that in an interesting edge u-v, u must be connected to all vertices v isn’t connected to, so u-v will be interesting iff cnt[i]= n-1-degree(v). Unfortunately we cannot do this for every vertex because that could take up to O(n^2) time.
Observation: If u-v is an interesting edge, the degree of at least one of u and v is \geq n/2.
Proof: If the degrees of u and v are both less than n/2, they are adjacent to less than n/2+n/2= n vertices in total, so this edge cannot be interesting.
The key fact now is that the number of vertices with degree \geq n/2 is quite small: in fact it’s at most 4m/n (otherwise the sum of degrees would exceed 4m/n \cdot n/2= 2m). Since n(n-1)/2\geq m, we have n \geq O(\sqrt{m}) \implies m/n \leq O(\sqrt{m}). This gives us a simple O((m+n)\sqrt{m}) solution: iterate over all vertices with degree \geq n/2, find the number of interesting edges passing through this vertex and add it to the answer. You must be careful about double counting some of the edges (or you could just insert the edges in a set and print the size of the set).