Connection Status:
Competition Arena > HalfGraph

HalfGraph

TCO19 SRM 751 · 2019-01-09 · by majk

TCO19 SRM 751 · 2019-01-09 · by majk · Graph Theory
Class Name: HalfGraph
Return Type: String[]
Method Name: compute
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Let G=(V,E) be an undirected graph.

A spanning subgraph of G is a graph that can be created by removing some (possibly empty) subset of edges from G. Note that a spanning subgraph must still contain all vertices of the original graph G.

A spanning subgraph H is called a half of G if the degree of every vertex v in H is exactly half of its degree in G.

You are given String[] a: the adjacency matrix of the graph G. More precisely, a[i][j] is '1' if vertices i and j are connected by an edge, and it is '0' if they are not.

Find and return the adjacency matrix of any graph that is a half of G. If there are multiple answers, you may return any one of them. If there are no answers, output an empty String[] instead.

Constraints

  • n will be between 1 and 50, inclusive.
  • a has exactly n elements.
  • Each element of a is a string of length n, consisting of characters '0' and '1' only.
  • The matrix is symmetric, i.e., for all i,j we have a[i][j] = a[j][i].
  • The main diagonal contains only characters '0'. In other words, the graph doesn't contain any loops.
Examples
0)
{"000",
 "000",
 "000"}
Returns: {"000", "000", "000" }

An empty graph is its own half, because the half of zero is zero.

1)
{"01111",
 "10111",
 "11011",
 "11101",
 "11110"}
Returns: {"00011", "00110", "01001", "11000", "10100" }

The input is a complete graph G on five vertices. In the graph G the degree of each vertex is 4. Thus, the output can be any subgraph of G that has 5 vertices and in which the degree of each vertex is 2.

2)
{"010",
 "101",
 "010"}
Returns: { }

This graph contains the edges 0-1 and 1-2. It does not have any half, because you cannot have a vertex of degree 1/2.

3)
{"01111",
 "10100",
 "11000",
 "10001",
 "10010"}
Returns: {"00011", "00100", "01000", "10000", "10000" }

Remember that the returned graph must be a subgraph of the original one. You are not allowed to add new edges, you may only erase the existing ones.

4)
{"01111","10111","11011","11101","11110"}
Returns: {"00011", "00110", "01001", "11000", "10100" }

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

Coding Area

Language: C++17 · define a public class HalfGraph with a public method vector<string> compute(vector<string> a) · 54 test cases · 2 s / 256 MB per case

Submitting as anonymous