18
1
Given a directed graph, output the longest cycle.
Rules
- Any reasonable input format is allowed (e.g. list of edges, connectivity matrix).
- The labels are not important, so you may impose any restrictions on the labels that you need and/or desire, so long as they do not contain additional information not given in the input (e.g. you can't require that the nodes in cycles are labeled with integers, and other nodes are labeled with alphabetic strings).
- A cycle is a sequence of nodes that are all connected, and no node is repeated, other than the node that is the start and end of the cycle (
[1, 2, 3, 1]
is a cycle, but[1, 2, 3, 2, 1]
is not). - If the graph is acyclic, the longest cycle has length 0, and thus should yield an empty output (e.g. empty list, no output at all).
- Repeating the first node at the end of the list of nodes in the cycle is optional (
[1, 2, 3, 1]
and[1, 2, 3]
denote the same cycle). - If there are multiple cycles of the same length, any one or all of them may be output.
- Builtins are allowed, but if your solution uses one, you are encouraged to include an alternate solution that does not use trivializing builtins (e.g. a builtin that outputs all cycles). However, the alternate solution will not count towards your score at all, so it is entirely optional.
Test Cases
In these test cases, input is given as a list of edges (where the first element is the source node and the second element is the destination node), and the output is a list of nodes without repetition of the first/last node.
[(0, 0), (0, 1)] -> [0]
[(0, 1), (1, 2)] -> []
[(0, 1), (1, 0)] -> [0, 1]
[(0, 1), (1, 2), (1, 3), (2, 4), (4, 5), (5, 1)] -> [1, 2, 4, 5]
[(0, 1), (0, 2), (1, 3), (2, 4), (3, 0), (4, 6), (6, 8), (8, 0)] -> [0, 2, 4, 6, 8]
[(0, 0), (0, 8), (0, 2), (0, 3), (0, 9), (1, 0), (1, 1), (1, 6), (1, 7), (1, 8), (1, 9), (2, 1), (2, 3), (2, 4), (2, 5), (3, 8), (3, 1), (3, 6), (3, 7), (4, 1), (4, 3), (4, 4), (4, 5), (4, 6), (4, 8), (5, 0), (5, 8), (5, 4), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 5), (8, 9), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)] -> [0, 9, 6, 7, 8, 2, 5, 4, 3, 1]
[(0, 0), (0, 2), (0, 4), (0, 5), (0, 7), (0, 9), (0, 11), (1, 2), (1, 4), (1, 5), (1, 8), (1, 9), (1, 10), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 0), (3, 1), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 11), (4, 1), (4, 3), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (5, 0), (5, 4), (5, 6), (5, 7), (5, 8), (5, 11), (6, 0), (6, 8), (6, 10), (6, 3), (6, 9), (7, 8), (7, 9), (7, 2), (7, 4), (7, 5), (8, 8), (8, 9), (8, 2), (8, 4), (8, 7), (9, 0), (9, 1), (9, 2), (9, 3), (9, 6), (9, 10), (9, 11), (10, 8), (10, 3), (10, 5), (10, 6), (11, 2), (11, 4), (11, 5), (11, 9), (11, 10), (11, 11)] -> [0, 11, 10, 6, 9, 3, 8, 7, 5, 4, 1, 2]
In all your examples, your output starts with the node with the smallest index. Is this a requirement? – Dada – 2017-01-18T20:49:15.397
@Dada No, that's just a coincidence with the test cases. The output should start (and optionally end) with the first node in the cycle. – Mego – 2017-01-18T20:50:38.740
You should pick a format, with endpoint or without is arbitrary and adds nothing to the challenge. – Magic Octopus Urn – 2017-01-18T20:51:52.753
5@carusocomputing I disagree. The last node is implicit if left off (since it's the same as the first node). Allowing the choice of whether or not to repeat the first node allows more freedom in golfing. – Mego – 2017-01-18T20:53:18.800
@Mego I thought you meant you had to handle either, then reread it and realized that that's the output format, not the input format. – Magic Octopus Urn – 2017-01-18T20:55:27.603
@Dada Yep, that was a relic from the original version of the challenge (which was simply to output the length, rather than the cycle). – Mego – 2017-01-18T21:54:18.293
1Related, kinda. – Fatalize – 2017-01-19T07:32:53.150