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 || len(graph) == 0 {
return false
}
// Three-color marking system:
// 0 = unvisited
// 1 = visiting (in current DFS path)
// 2 = visited (completed)
colors := make(map[string]int)
// Helper function to perform DFS
var dfs func(node string) bool
dfs = func(node string) bool {
// If node is currently being visited, we found a cycle
if colors[node] == 1 {
return true
}
// If node is already visited, no cycle from here
if colors[node] == 2 {
return false
}
// Mark as visiting
colors[node] = 1
// Visit all neighbors
for _, neighbor := range graph[node] {
if dfs(neighbor) {
return true
}
}
// Mark as visited
colors[node] = 2
return false
}
// Check each node
for node := range graph {
if colors[node] == 0 {
if dfs(node) {
return true
}
}
}
return false
}
```Test output (stdout)
ackage":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle"}
{"Time":"2026-07-03T00:39:24.575169659+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-03T00:39:24.575171099+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-03T00:39:24.575172249+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Elapsed":0}
{"Time":"2026-07-03T00:39:24.575173179+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle"}
{"Time":"2026-07-03T00:39:24.575173919+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"=== RUN TestHasCycle/duplicate_edges,_no_cycle\n"}
{"Time":"2026-07-03T00:39:24.575176039+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-03T00:39:24.575177279+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Elapsed":0}
{"Time":"2026-07-03T00:39:24.575179489+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle"}
{"Time":"2026-07-03T00:39:24.575180529+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"=== RUN TestHasCycle/duplicate_edges_forming_cycle\n"}
{"Time":"2026-07-03T00:39:24.575181599+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-03T00:39:24.575182519+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Elapsed":0}
{"Time":"2026-07-03T00:39:24.575183509+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle"}
{"Time":"2026-07-03T00:39:24.575184259+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"=== RUN TestHasCycle/long_chain_no_cycle\n"}
{"Time":"2026-07-03T00:39:24.575185449+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-03T00:39:24.575187359+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Elapsed":0}
{"Time":"2026-07-03T00:39:24.575188269+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain"}
{"Time":"2026-07-03T00:39:24.575190379+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"=== RUN TestHasCycle/cycle_deep_in_chain\n"}
{"Time":"2026-07-03T00:39:24.575191459+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-03T00:39:24.575193129+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Elapsed":0}
{"Time":"2026-07-03T00:39:24.575194159+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle","Output":"--- PASS: TestHasCycle (0.00s)\n"}
{"Time":"2026-07-03T00:39:24.575195269+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle","Elapsed":0}
{"Time":"2026-07-03T00:39:24.575196169+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-07-03T00:39:24.575223979+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-07-03T00:39:24.575228459+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}