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)
}
})
}
}
Proposed solution
```go
package challenge
func HasCycle(graph map[string][]string) bool {
if len(graph) == 0 {
return false
}
// Collect all unique nodes (both keys and values)
allNodes := make(map[string]bool)
for k, neighbors := range graph {
allNodes[k] = true
for _, n := range neighbors {
allNodes[n] = true
}
}
// State: 0 = unvisited, 1 = visiting, 2 = visited
state := make(map[string]int)
for node := range allNodes {
state[node] = 0
}
var dfs func(string) bool
dfs = func(node string) bool {
state[node] = 1 // Mark as currently visiting
for _, neighbor := range graph[node] {
if state[neighbor] == 1 {
return true // Back edge found → cycle
}
if state[neighbor] == 0 {
if dfs(neighbor) {
return true
}
}
}
state[node] = 2 // Mark as fully visited
return false
}
// Run DFS from each unvisited node to handle disconnected components
for node := range allNodes {
if state[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-06-29T19:35:42.004343433+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-06-29T19:35:42.004344833+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-06-29T19:35:42.004345833+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Elapsed":0}
{"Time":"2026-06-29T19:35:42.004348043+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle"}
{"Time":"2026-06-29T19:35:42.004348843+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"=== RUN TestHasCycle/duplicate_edges,_no_cycle\n"}
{"Time":"2026-06-29T19:35:42.004351033+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"--- PASS: TestHasCycle/duplicate_edges,_no_cycle (0.00s)\n"}
{"Time":"2026-06-29T19:35:42.004352533+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Elapsed":0}
{"Time":"2026-06-29T19:35:42.004353983+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle"}
{"Time":"2026-06-29T19:35:42.004354803+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"=== RUN TestHasCycle/duplicate_edges_forming_cycle\n"}
{"Time":"2026-06-29T19:35:42.004356203+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"--- PASS: TestHasCycle/duplicate_edges_forming_cycle (0.00s)\n"}
{"Time":"2026-06-29T19:35:42.004357193+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Elapsed":0}
{"Time":"2026-06-29T19:35:42.004358043+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle"}
{"Time":"2026-06-29T19:35:42.004358843+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"=== RUN TestHasCycle/long_chain_no_cycle\n"}
{"Time":"2026-06-29T19:35:42.004359903+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"--- PASS: TestHasCycle/long_chain_no_cycle (0.00s)\n"}
{"Time":"2026-06-29T19:35:42.004361273+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Elapsed":0}
{"Time":"2026-06-29T19:35:42.004362733+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain"}
{"Time":"2026-06-29T19:35:42.004363483+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"=== RUN TestHasCycle/cycle_deep_in_chain\n"}
{"Time":"2026-06-29T19:35:42.004365023+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"--- PASS: TestHasCycle/cycle_deep_in_chain (0.00s)\n"}
{"Time":"2026-06-29T19:35:42.004365993+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Elapsed":0}
{"Time":"2026-06-29T19:35:42.004367083+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle","Output":"--- PASS: TestHasCycle (0.00s)\n"}
{"Time":"2026-06-29T19:35:42.004368123+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle","Elapsed":0}
{"Time":"2026-06-29T19:35:42.004369463+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-06-29T19:35:42.004391472+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-06-29T19:35:42.004396142+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}