PaintItBlack | Topcoder Archive

Problem Statement

You are given an undirected connected simple graph with n nodes, numbered 0, 1, ..., n-1. The edges of the graph are given in the int[]s a and b: for each valid i, there is an undirected edge between a[i] and b[i].

You are currently in the vertex u and all the vertices are colored white. Whenever you go from some vertex p to some vertex q, you must toggle the color of q (from white to black and vice versa). Note that p's color remains unchanged.

Find whether there is a closed walk (starting and ending at u) with less than or equal to 5 * n moves which will leave all the vertices colored black. (Note that each edge can be traversed any number of times in both directions.)

If there is a solution, return a int[] describing one solution by listing the order in which it visits nodes (including u both at the beginning and at the end). Otherwise, return an empty int[].

Definition

Class:: PaintItBlack
Method:: findWalk
Parameters:: int, int, int[], int[]
Returns:: int[]
Method signature:: int[] findWalk(int n, int u, int[] a, int[] b)
(be sure your method is public)

Notes

You do not have to minimize the length of the returned walk.

Constraints

n will be between 2 and 200 inclusive.
u will be between 0 and n - 1 inclusive.
a will have between n - 1 and 1000 elements inclusive.
a and b will have the same number of elements.
Every element of a and b will be between 0 and n - 1 inclusive.
The graph described by n, a, b will be a simple undirected connected graph.

Examples

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

{0, 1, 2, 3}

{1, 2, 3, 0}

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

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.