go-03-detect-cycle
1.000
Challenge · difficulty 3/5
# Detect cycle in a directed graph
Implement **`solution.go`** in `package challenge` exporting:
```go
func HasCycle(graph map[string][]string) bool
```
The graph is given as an adjacency map: each key is a node, and its value is the slice of
nodes it has directed edges to. Return `true` if the directed graph contains **any cycle**,
and `false` otherwise.
Rules:
- A **self-loop** (`"a" -> "a"`) counts as a cycle.
- A neighbor that does not appear as a key in the map is a valid node with no outgoing edges.
- An empty map (or `nil`) has no cycle → `false`.
- Duplicate edges are allowed and must not break detection.
Examples:
- `HasCycle(map[string][]string{"a": {"b"}, "b": {"c"}, "c": {}})` → `false` (a DAG)
- `HasCycle(map[string][]string{"a": {"a"}})` → `true` (self-loop)
- `HasCycle(map[string][]string{"a": {"b"}, "b": {"c"}, "c": {"a"}})` → `true` (3-node cycle)
- `HasCycle(map[string][]string{})` → `false`
tests/solution_test.go
package challenge
import "testing"
func TestHasCycle(t *testing.T) {
cases := []struct {
name string
graph map[string][]string
want bool
}{
{
name: "nil graph",
graph: nil,
want: false,
},
{
name: "empty graph",
graph: map[string][]string{},
want: false,
},
{
name: "single node no edges",
graph: map[string][]string{"a": {}},
want: false,
},
{
name: "simple DAG",
graph: map[string][]string{"a": {"b"}, "b": {"c"}, "c": {}},
want: false,
},
{
name: "diamond DAG (shared descendant, no cycle)",
graph: map[string][]string{
"a": {"b", "c"},
"b": {"d"},
"c": {"d"},
"d": {},
},
want: false,
},
{
name: "self-loop",
graph: map[string][]string{"a": {"a"}},
want: true,
},
{
name: "two node cycle",
graph: map[string][]string{"a": {"b"}, "b": {"a"}},
want: true,
},
{
name: "three node cycle",
graph: map[string][]string{"a": {"b"}, "b": {"c"}, "c": {"a"}},
want: true,
},
{
name: "cycle reachable only from one component",
graph: map[string][]string{
"x": {"y"},
"y": {},
"a": {"b"},
"b": {"c"},
"c": {"b"},
},
want: true,
},
{
name: "neighbor not a key (implicit leaf), no cycle",
graph: map[string][]string{
"a": {"b"},
"b": {"c"}, // c is not a key
},
want: false,
},
{
name: "duplicate edges, no cycle",
graph: map[string][]string{
"a": {"b", "b", "b"},
"b": {},
},
want: false,
},
{
name: "duplicate edges forming cycle",
graph: map[string][]string{
"a": {"b", "b"},
"b": {"a", "a"},
},
want: true,
},
{
name: "long chain no cycle",
graph: map[string][]string{
"a": {"b"}, "b": {"c"}, "c": {"d"}, "d": {"e"}, "e": {"f"}, "f": {},
},
want: false,
},
{
name: "cycle deep in chain",
graph: map[string][]string{
"a": {"b"}, "b": {"c"}, "c": {"d"}, "d": {"e"}, "e": {"c"},
},
want: true,
},
}
for _, c := range cases {
t.Run(c.name, func(t *testing.T) {
if got := HasCycle(c.graph); got != c.want {
t.Errorf("HasCycle(%v) = %v, want %v", c.graph, got, c.want)
}
})
}
}
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.Proposed solution
```go
package challenge
func HasCycle(graph map[string][]string) bool {
if graph == nil {
return false
}
visited := make(map[string]bool)
recursionStack := make(map[string]bool)
var hasCycleHelper func(node string) bool
hasCycleHelper = func(node string) bool {
if recursionStack[node] {
return true
}
if visited[node] {
return false
}
visited[node] = true
recursionStack[node] = true
for _, neighbor := range graph[node] {
if hasCycleHelper(neighbor) {
return true
}
}
recursionStack[node] = false
return false
}
for node := range graph {
if !visited[node] {
if hasCycleHelper(node) {
return true
}
}
}
return false
}
```Test output (stdout)
ackage":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle"}
{"Time":"2026-07-22T02:20:18.314617999+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Output":"=== RUN TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle\n"}
{"Time":"2026-07-22T02:20:18.314619889+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Output":"--- PASS: TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle (0.00s)\n"}
{"Time":"2026-07-22T02:20:18.314622089+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Elapsed":0}
{"Time":"2026-07-22T02:20:18.314623359+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle"}
{"Time":"2026-07-22T02:20:18.314624289+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"=== RUN TestHasCycle/duplicate_edges,_no_cycle\n"}
{"Time":"2026-07-22T02:20:18.314625459+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"--- PASS: TestHasCycle/duplicate_edges,_no_cycle (0.00s)\n"}
{"Time":"2026-07-22T02:20:18.314626399+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Elapsed":0}
{"Time":"2026-07-22T02:20:18.314627379+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle"}
{"Time":"2026-07-22T02:20:18.314628179+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"=== RUN TestHasCycle/duplicate_edges_forming_cycle\n"}
{"Time":"2026-07-22T02:20:18.314629299+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"--- PASS: TestHasCycle/duplicate_edges_forming_cycle (0.00s)\n"}
{"Time":"2026-07-22T02:20:18.314631709+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Elapsed":0}
{"Time":"2026-07-22T02:20:18.314632569+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle"}
{"Time":"2026-07-22T02:20:18.314633309+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"=== RUN TestHasCycle/long_chain_no_cycle\n"}
{"Time":"2026-07-22T02:20:18.314634729+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"--- PASS: TestHasCycle/long_chain_no_cycle (0.00s)\n"}
{"Time":"2026-07-22T02:20:18.314636139+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Elapsed":0}
{"Time":"2026-07-22T02:20:18.314637249+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain"}
{"Time":"2026-07-22T02:20:18.314638159+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"=== RUN TestHasCycle/cycle_deep_in_chain\n"}
{"Time":"2026-07-22T02:20:18.314639379+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"--- PASS: TestHasCycle/cycle_deep_in_chain (0.00s)\n"}
{"Time":"2026-07-22T02:20:18.314640629+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Elapsed":0}
{"Time":"2026-07-22T02:20:18.314641689+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle","Output":"--- PASS: TestHasCycle (0.00s)\n"}
{"Time":"2026-07-22T02:20:18.314642869+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle","Elapsed":0}
{"Time":"2026-07-22T02:20:18.314644039+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-07-22T02:20:18.314840679+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-07-22T02:20:18.314850729+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}