Detecting an Odd Length Cycle
Given an undirected graph as an adjacency list, return whether the graph has an odd length cycle.
Constraints
n, m ≤ 250wherenandmare the number of rows and columns ingraph
https://binarysearch.com/problems/Detecting-an-Odd-Length-Cycle
ExamplesPermalink
Example 1Permalink
Input
- graph =
[[1],
[0]]
Output
- answer =
False
Explanation
There is an even length cycle, not odd.
Example 2Permalink
Input
- graph =
[[list([1, 2, 3]),list([0, 2]),list([0, 1, 3]),list([0, 2])]]
Output
- answer =
True
Explanation
One odd length cycle would be 0 -> 2 -> 1 -> 0
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def bipartite(graph): | |
| labels = {} | |
| def solveR(i, label): | |
| if i in labels: | |
| return label == labels[i] | |
| labels[i] = label | |
| return all(solveR(j, 1 - label) for j in graph[i]) | |
| return all(solveR(i, 0) for i in range(len(graph)) if i not in labels) | |
| def solve(self, graph): | |
| # graph has odd length cycle(s) if it is not bipartite | |
| return not Solution.bipartite(graph) |
Leave a comment