Connection Status:
Competition Arena > ColoringEdgesDiv1

ColoringEdgesDiv1

2018 TCO Fun 3A · 2018-04-20 · by ltdtl

2018 TCO Fun 3A · 2018-04-20 · by ltdtl · Graph Theory, Greedy
Class Name: ColoringEdgesDiv1
Return Type: int[]
Method Name: findColoring
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 3-regular graph is a simple graph such that the degree of each vertex is 3.


You are given a 3-regular (simple) graph. Given such a graph, you want to color the edges as either 0 or 1 such that the graph does not contain a cycle that consists of edges of the same color.


You are given an int n (the number of nodes), and two int[]'s x and y that describe a 3-regular graph. For each i between 0 and n-1 (inclusive), (x[i], y[i]) describe an edge in this graph.


You must return an array of integers (int[]) of length exactly (n*3)/2 where each element is either 0 or 1. The i-th element in your answer describes the color of the edge (x[i], y[i]). If there exist multiple ways to color the edges such that the colored graph does not contain a cycle consisting of edges of the same color, you may return any one of them.

Notes

  • There is always a way to color the edges using two colors such that no cycle of the same color exists.

Constraints

  • n will be an even integer between 4 and 1,000, inclusive.
  • x will contain exactly (n*3)/2 elements.
  • y will contain exactly (n*3)/2 elements.
  • Each element of x will be between 0 and n-1, inclusive.
  • Each element of y will be between 0 and n-1, inclusive.
  • x[i] ≠ y[i] will hold for all i between 0 and n-1, inclusive.
  • (x[i], y[i]) ≠ (x[j], y[j]) will hold for all i,j with 0 ≤ i < j ≤ n-1.
  • Edges will be distinct.
  • Each vertex will have degree 3.
Examples
0)
6
{2, 0, 3, 1, 1, 0, 0, 2, 4}
{3, 3, 1, 5, 4, 2, 4, 5, 5}
Returns: {0, 1, 0, 1, 0, 1, 0, 0, 1 }
1)
6
{3, 5, 4, 1, 4, 2, 0, 1, 2}
{4, 2, 1, 3, 5, 0, 5, 0, 3}
Returns: {0, 0, 0, 1, 1, 1, 0, 1, 0 }
2)
8
{0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3}
{1, 2, 3, 4, 5, 6, 7, 0, 4, 5, 7, 6}
Returns: {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 }
3)
6
{0, 1, 2, 3, 4, 5, 0, 1, 2}
{1, 2, 3, 4, 5, 0, 3, 4, 5}
Returns: {1, 0, 1, 0, 1, 0, 1, 0, 1 }
4)
4
{0, 1, 2, 3, 0, 1}
{1, 2, 3, 0, 2, 3}
Returns: {0, 1, 0, 1, 0, 1 }

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

Coding Area

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

Submitting as anonymous