ColoringEdgesDiv1 | Topcoder Archive

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.

Definition

Class:: ColoringEdgesDiv1
Method:: findColoring
Parameters:: int, int[], int[]
Returns:: int[]
Method signature:: int[] findColoring(int n, int[] x, int[] y)
(be sure your method is public)

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

{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 }

{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 }

{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 }

{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 }

{0, 1, 2, 3, 0, 1}

{1, 2, 3, 0, 2, 3}

Returns: {0, 1, 0, 1, 0, 1 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.