MinDegreeSubgraph

SRM 736 *TCO19* · 2018-08-14 · by majk

SRM 736 *TCO19* · 2018-08-14 · by majk · Graph Theory, Greedy

Show categories

Class Name: MinDegreeSubgraph

Return Type: String

Method Name: exists

Arg Types: (int, long long, int)

Problem Statement

All graphs in this problem are undirected simple graphs. (I.e., each pair of vertices is connected by at most one edge, and there are no loops.)

Let G=(V,E) be a graph. We call a graph H=(V',E') a subgraph of a graph G if the following conditions hold:

V' is a nonempty subset of V
E' is a subset of E
for each edge in E', both its endpoints are in V'

In other words, a subgraph can be constructed by first removing some vertices (possibly none, but not all of them) together with all their edges, and then removing some of the remaining edges (possibly none or all of them).

The mindegree of a graph is the minimum of the degrees of its vertices.

A graph is locally k-dense if it contains a subgraph with mindegree k.

You are given an int n, a long m, and an int k. Consider all graphs on n vertices with exactly m edges. Determine whether all, some, or none of these graphs are locally k-dense. Return "ALL", "SOME", or "NONE", respectively.

Notes

Given the constraints of the problem, there always exists at least one graph with n vertices and m edges.
Given a graph, the degree of a vertex is the number of edges incident with this vertex.
The return value "SOME" means that there exists a graph with the desired property and also a graph without the desired property.

Constraints

n will be between 1 and 109, inclusive.
m will be between 0 and n(n-1)/2, inclusive.
k will be between 0 and 109, inclusive.

Examples

3
3
2
Returns: "ALL"

Up to isomorphism, there is only one graph on 3 vertices and 3 edges: the triangle. It does have a subgraph with mindegree 2: itself. (Note that each graph is its own subgraph.)

4
3
2
Returns: "SOME"

Two of the graphs with 4 vertices and 3 edges are trees. Obviously, a tree cannot be locally 2-dense, because each subgraph of a tree is a forest, and each forest contains a vertex of degree at most 1. Another graph with 4 vertices and 3 edges is a graph that consists of a triangle and an isolated vertex. This graph is locally 2-dense because it contains a subgraph with mindegree 2: the triangle.

6
10
3
Returns: "ALL"

There are many graphs with 6 vertices and 10 edges. No matter which one of them we choose, it will always contain some subgraph with mindegree exactly 3.

6
15
4
Returns: "ALL"

There is only one such graph: the complete graph K6. It contains many mindegree-4 subgraphs. For instance, we can construct such a subgraph by removing any one vertex, and we can also construct a different mindegree-4 subgraph by removing any one edge.

17
53
11
Returns: "NONE"

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

Coding Area

Language: C++17 · define a public class MinDegreeSubgraph with a public method string exists(int n, long long m, int k) · 101 test cases · 2 s / 256 MB per case