Connection Status:
Competition Arena > MakingRegularGraph

MakingRegularGraph

TCO18 Fun 2A · 2018-04-20 · by ltdtl

TCO18 Fun 2A · 2018-04-20 · by ltdtl · Graph Theory, Greedy
Class Name: MakingRegularGraph
Return Type: int[]
Method Name: addEdges
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

Problem Statement

A simple graph is an undirected graph in which each edge connects two different vertices and each pair of vertices is connected by at most one edge. In other words, there are no self-loops and no multiple edges.


A 2-regular graph is a simple graph such that the degree of each vertex is 2.


You are given the int n and two int[]s x and y. These variables describe a simple graph G on n vertices, labeled 0 through n-1. For each valid i, the graph G contains an edge that connects the vertices x[i] and y[i]. It is guaranteed that each vertex in G has degree 2 or less.


You want to change G into a 2-regular graph by adding some edges. Determine whether this can be done, and if yes, find the lexicographically smallest way of doing so. A more precise definition of the task follows.


An encoding of a set of k edges is any int[] E of length 2k such that the set of edges is equal to the set { (E[0], E[1]), (E[2], E[3]), ... }. For example, suppose you have the edges (1,7) and (2,5). Then {1,7,5,2} and {2,5,1,7} are two of the valid encodings. On the other hand, {1,2,5,7} is not a valid encoding.


If changing G into a 2-regular graph is impossible, return the int[] {-1}, i.e., an array that contains only one integer, -1. Otherwise, find and return the lexicographically smallest encoding of a set of edges that should be added to G in order to make it 2-regular.

Notes

  • Given two different int[]s S and T with the same number of elements, the lexicographically smaller one is the one that has a smaller element at the first index at which they differ.

Constraints

  • n will be between 1 and 1,000, inclusive.
  • x will contain between 0 and n-1 elements, inclusive.
  • y will contain the same number of elements as x.
  • Each element of x will be between 0 and n-2, inclusive.
  • Each element of y will be between 1 and n-1, inclusive.
  • x[i] < y[i] will hold for all i (i.e., no self-loops).
  • In a graph described by n, x, and y, every vertex will have degree 2 or less (For every integer v between 0 and n-1, v appears at most twice in x and y combined).
  • In a graph described by n, x, and y, there will be at most one edge between a pair of vertices (two equalities (x[i] = x[j] and y[i] = y[j]) will hold only when i = j).
Examples
0)
6
{0,2}
{2,3}
Returns: {0, 1, 1, 4, 3, 5, 4, 5 }

There are many ways to turn this G into a 2-regular graph. For example, you may: add the edges (3, 4), (4, 5), (5, 1), (1, 0) to obtain one large cycle of length 6 add the edges (3, 5), (5, 4), (4, 1), (1, 0) to obtain another cycle of length 6 add the edges (0, 3), (1, 4), (4, 5), (1, 5) to obtain two cycles of length 3 each ... Each of these options has multiple encodings. The return value shown above is the lexicographically smallest out of all encodings of all options. It corresponds to the second set of edges listed above.

1)
4
{1,2,1}
{2,3,3}
Returns: {-1 }

The given graph contains a cycle of length 3 and an isolated vertex. Unfortunately, we cannot turn this into a 2-reguglar graph.

2)
3
{}
{}
Returns: {0, 1, 0, 2, 1, 2 }

x and y can be empty, meaning there are no edges present. In this example, there is a unique set of edges we can add in order to create a 2-regular graph: (0, 1), (0, 2), and (1, 2). However, there exist many different ways to describe these three edges. For instance, both {0, 1, 2, 0, 2, 1} and {0, 1, 0, 2, 1, 2} describe the same set of edges. Recall that you must return the one that comes lexicographically first.

3)
5
{0}
{4}
Returns: {0, 1, 1, 2, 2, 3, 3, 4 }
4)
5
{2}
{3}
Returns: {0, 1, 0, 2, 1, 4, 3, 4 }

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

Coding Area

Language: C++17 · define a public class MakingRegularGraph with a public method vector<int> addEdges(int n, vector<int> x, vector<int> y) · 154 test cases · 2 s / 256 MB per case

Submitting as anonymous