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-01T23:35:11.727715628+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-01T23:35:11.727717008+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-01T23:35:11.727718468+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Elapsed":0}
{"Time":"2026-07-01T23:35:11.727719378+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle"}
{"Time":"2026-07-01T23:35:11.727720678+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"=== RUN TestHasCycle/duplicate_edges,_no_cycle\n"}
{"Time":"2026-07-01T23:35:11.727722268+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-01T23:35:11.727723548+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Elapsed":0}
{"Time":"2026-07-01T23:35:11.727724618+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle"}
{"Time":"2026-07-01T23:35:11.727725398+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"=== RUN TestHasCycle/duplicate_edges_forming_cycle\n"}
{"Time":"2026-07-01T23:35:11.727726538+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-01T23:35:11.727727678+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Elapsed":0}
{"Time":"2026-07-01T23:35:11.727728588+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle"}
{"Time":"2026-07-01T23:35:11.727729328+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"=== RUN TestHasCycle/long_chain_no_cycle\n"}
{"Time":"2026-07-01T23:35:11.727730478+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-01T23:35:11.727732368+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Elapsed":0}
{"Time":"2026-07-01T23:35:11.727733239+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain"}
{"Time":"2026-07-01T23:35:11.727734169+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"=== RUN TestHasCycle/cycle_deep_in_chain\n"}
{"Time":"2026-07-01T23:35:11.727735719+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-01T23:35:11.727736739+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Elapsed":0}
{"Time":"2026-07-01T23:35:11.727737789+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle","Output":"--- PASS: TestHasCycle (0.00s)\n"}
{"Time":"2026-07-01T23:35:11.727738839+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle","Elapsed":0}
{"Time":"2026-07-01T23:35:11.727739929+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-07-01T23:35:11.727806719+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-07-01T23:35:11.727825949+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}