Connection Status:
Competition Arena > OddCycleDetector

OddCycleDetector

TCO20 Wildcard Parallel · 2020-10-06 · by misof

TCO20 Wildcard Parallel · 2020-10-06 · by misof · Graph Theory
Class Name: OddCycleDetector
Return Type: int[]
Method Name: detect
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given an undirected graph with N vertices. The vertices are numbered from 0 to N-1. You are given the adjacency matrix of this graph in the String[] G. (G[i][j] is 'Y' if i and j are adjacent, or 'N' if they are not.)

A simple odd cycle is a sequence of vertices V[0], V[1], ..., V[l-1] such that:

  • l is at least 3.
  • l is odd.
  • All V[i] are distinct.
  • For each i, V[i] and V[i+1] are adjacent.
  • V[l-1] and V[0] are adjacent.

A vertex is happy if there is a simple odd cycle that passes through this vertex. The certificate of happiness is any simple odd cycle that contains this vertex. If a vertex isn't happy, its certificate of happiness is an empty sequence.

Return a int[] of the form C[0] + {-1} + C[1] + {-1} + ... + {-1} + C[N-1], where each C[i] is any certificate of happiness of vertex i.

Constraints

  • N will be between 1 and 50, inclusive.
  • G will contain N elements.
  • Each element of G will contain N characters.
  • Each character in G will be either 'Y' or 'N'.
  • For each i, G[i][i] will be 'N'.
  • For each i and j, G[i][j] will be equal to G[j][i].
Examples
0)
{"NYNN",
 "YNYN",
 "NYNY",
 "NNYN"}
Returns: {-1, -1, -1 }

This graph is the path 0-1-2-3. There are no odd cycles anywhere.

1)
{"NYNN",
 "YNYY",
 "NYNY",
 "NYYN"}
Returns: {-1, 3, 2, 1, -1, 3, 2, 1, -1, 3, 2, 1 }

Compared to Example 0 we now also have the edge 1-3. The vertices 1, 2, 3 now lie on the odd cycle {1, 2, 3}. 0 - 1 / | 2 - 3

2)
{"NYYY",
 "YNYN",
 "YYNY",
 "YNYN"}
Returns: {2, 1, 0, -1, 2, 1, 0, -1, 2, 1, 0, -1, 0, 3, 2 }

Each vertex lies on some odd cycle, although not all of them on the same one. 0 - 1 | \ | 3 - 2

3)
{"NNYYN",
 "NNNYY",
 "YNNNY",
 "YYNNN",
 "NYYNN"}
Returns: {3, 1, 4, 2, 0, -1, 3, 1, 4, 2, 0, -1, 3, 1, 4, 2, 0, -1, 3, 1, 4, 2, 0, -1, 3, 1, 4, 2, 0 }

The entire graph is an odd cycle {0, 2, 4, 1, 3}.

4)
{"N"}
Returns: { }

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

Coding Area

Language: C++17 · define a public class OddCycleDetector with a public method vector<int> detect(vector<string> G) · 232 test cases · 2 s / 256 MB per case

Submitting as anonymous