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
// HasCycle detects if a directed graph contains a cycle.
// It uses Depth-First Search (DFS) with three states:
// - 0: unvisited
// - 1: visiting (in current DFS path)
// - 2: visited (fully processed)
func HasCycle(graph map[string][]string) bool {
if graph == nil {
return false
}
// Initialize state map for all nodes
// Nodes that only appear as neighbors but not as keys are also tracked
visited := make(map[string]int)
// Collect all unique nodes from keys and values
nodes := make(map[string]bool)
for node := range graph {
nodes[node] = true
for _, neighbor := range graph[node] {
nodes[neighbor] = true
}
}
// Perform DFS from each unvisited node
for node := range nodes {
if visited[node] == 0 {
if dfsHasCycle(node, graph, visited) {
return true
}
}
}
return false
}
func dfsHasCycle(node string, graph map[string][]string, visited map[string]int) bool {
// Mark node as being visited (in current path)
visited[node] = 1
// Check all neighbors
for _, neighbor := range graph[node] {
switch visited[neighbor] {
case 0:
// If neighbor is unvisited, recurse
if dfsHasCycle(neighbor, graph, visited) {
return true
}
case 1:
// If neighbor is currently in the path, we found a cycle
return true
}
}
// Mark node as fully visited (no cycle found in its subtree)
visited[node] = 2
return false
}
```Test output (stdout)
ackage":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle"}
{"Time":"2026-07-02T00:04:41.076954795+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-02T00:04:41.076956385+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-02T00:04:41.076957385+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Elapsed":0}
{"Time":"2026-07-02T00:04:41.076958295+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle"}
{"Time":"2026-07-02T00:04:41.076959105+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"=== RUN TestHasCycle/duplicate_edges,_no_cycle\n"}
{"Time":"2026-07-02T00:04:41.076960775+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-02T00:04:41.076961775+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Elapsed":0}
{"Time":"2026-07-02T00:04:41.076962965+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle"}
{"Time":"2026-07-02T00:04:41.076963935+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"=== RUN TestHasCycle/duplicate_edges_forming_cycle\n"}
{"Time":"2026-07-02T00:04:41.076965175+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-02T00:04:41.076966055+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Elapsed":0}
{"Time":"2026-07-02T00:04:41.076966965+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle"}
{"Time":"2026-07-02T00:04:41.076967715+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"=== RUN TestHasCycle/long_chain_no_cycle\n"}
{"Time":"2026-07-02T00:04:41.076969325+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-02T00:04:41.076970655+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Elapsed":0}
{"Time":"2026-07-02T00:04:41.076971545+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain"}
{"Time":"2026-07-02T00:04:41.076972315+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"=== RUN TestHasCycle/cycle_deep_in_chain\n"}
{"Time":"2026-07-02T00:04:41.076974165+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-02T00:04:41.076975445+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Elapsed":0}
{"Time":"2026-07-02T00:04:41.076976505+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle","Output":"--- PASS: TestHasCycle (0.00s)\n"}
{"Time":"2026-07-02T00:04:41.076977535+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle","Elapsed":0}
{"Time":"2026-07-02T00:04:41.076978465+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-07-02T00:04:41.077165107+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-07-02T00:04:41.077186677+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}