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.
Definition
- Class:
- OddCycleDetector
- Method:
- detect
- Parameters:
- String[]
- Returns:
- int[]
- Method signature:
- int[] detect(String[] G)
- (be sure your method is public)
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
{"NYNN", "YNYN", "NYNY", "NNYN"}Returns: {-1, -1, -1 }This graph is the path 0-1-2-3. There are no odd cycles anywhere.{"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{"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{"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}.