×

Contest
Practice

## 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).

This question is marked "community wiki".

15718
accept rate: 10%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,497
×3,709
×353
×23
×8

question asked: 01 Mar '16, 02:19

question was seen: 1,225 times

last updated: 19 Apr '16, 21:13