go-03-detect-cycle

# 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`

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)
			}
		})
	}
}

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.

```go
package challenge

func HasCycle(graph map[string][]string) bool {
	if graph == nil || len(graph) == 0 {
		return false
	}

	// States: 0 = unvisited, 1 = visiting (in current DFS path), 2 = visited (completed)
	state := make(map[string]int)

	var dfs func(node string) bool
	dfs = func(node string) bool {
		// If node not in graph, it has no outgoing edges, so no cycle from here
		if _, exists := state[node]; !exists {
			return false
		}

		// If we've already finished processing this node, no cycle through it
		if state[node] == 2 {
			return false
		}

		// If we're currently visiting this node, we found a cycle
		if state[node] == 1 {
			return true
		}

		// Mark as visiting
		state[node] = 1

		// Visit all neighbors
		for _, neighbor := range graph[node] {
			if dfs(neighbor) {
				return true
			}
		}

		// Mark as fully visited
		state[node] = 2
		return false
	}

	// Check each node in the graph for cycles
	for node := range graph {
		if state[node] == 0 { // Unvisited
			if dfs(node) {
				return true
			}
		}
	}

	return false
}
```

[
  {
    "total": 1,
    "answer": "```go\npackage challenge\n\nfunc HasCycle(graph map[string][]string) bool {\n\tif graph == nil || len(graph) == 0 {\n\t\treturn false\n\t}\n\n\t// States: 0 = unvisited, 1 = visiting (in current DFS path), 2 = visited (completed)\n\tstate := make(map[string]int)\n\n\tvar dfs func(node string) bool\n\tdfs = func(node string) bool {\n\t\t// If node not in graph, it has no outgoing edges, so no cycle from here\n\t\tif _, exists := state[node]; !exists {\n\t\t\treturn false\n\t\t}\n\n\t\t// If we've already finished processing this node, no cycle through it\n\t\tif state[node] == 2 {\n\t\t\treturn false\n\t\t}\n\n\t\t// If we're currently visiting this node, we found a cycle\n\t\tif state[node] == 1 {\n\t\t\treturn true\n\t\t}\n\n\t\t// Mark as visiting\n\t\tstate[node] = 1\n\n\t\t// Visit all neighbors\n\t\tfor _, neighbor := range graph[node] {\n\t\t\tif dfs(neighbor) {\n\t\t\t\treturn true\n\t\t\t}\n\t\t}\n\n\t\t// Mark as fully visited\n\t\tstate[node] = 2\n\t\treturn false\n\t}\n\n\t// Check each node in the graph for cycles\n\tfor node := range graph {\n\t\tif state[node] == 0 { // Unvisited\n\t\t\tif dfs(node) {\n\t\t\t\treturn true\n\t\t\t}\n\t\t}\n\t}\n\n\treturn false\n}\n```",
    "passed": 0,
    "test_error": "lse, want true\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835484355+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/duplicate_edges_forming_cycle\",\"Output\":\"--- FAIL: TestHasCycle/duplicate_edges_forming_cycle (0.00s)\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835485335+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/duplicate_edges_forming_cycle\",\"Elapsed\":0}\n{\"Time\":\"2026-07-01T22:48:06.835486265+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/long_chain_no_cycle\"}\n{\"Time\":\"2026-07-01T22:48:06.835487055+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/long_chain_no_cycle\",\"Output\":\"=== RUN   TestHasCycle/long_chain_no_cycle\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835488155+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/long_chain_no_cycle\",\"Output\":\"--- PASS: TestHasCycle/long_chain_no_cycle (0.00s)\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835490115+02:00\",\"Action\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/long_chain_no_cycle\",\"Elapsed\":0}\n{\"Time\":\"2026-07-01T22:48:06.835491265+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\"}\n{\"Time\":\"2026-07-01T22:48:06.835492085+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\",\"Output\":\"=== RUN   TestHasCycle/cycle_deep_in_chain\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835493125+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\",\"Output\":\"    solution_test.go:110: HasCycle(map[a:[b] b:[c] c:[d] d:[e] e:[c]]) = false, want true\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835494245+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\",\"Output\":\"--- FAIL: TestHasCycle/cycle_deep_in_chain (0.00s)\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835495515+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\",\"Elapsed\":0}\n{\"Time\":\"2026-07-01T22:48:06.835496595+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle\",\"Output\":\"--- FAIL: TestHasCycle (0.00s)\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835497635+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle\",\"Elapsed\":0}\n{\"Time\":\"2026-07-01T22:48:06.835498615+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835675266+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge\\t0.001s\\n\"}\n{\"Time\":\"2026-07-01T22:48:06.835685386+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0.001}"
  },
  {
    "total": 1,
    "answer": "Looking at the test failures, I can see two issues:\n\n1. The `duplicate_edges_forming_cycle` test is failing (want true, got false)\n2. The `cycle_deep_in_chain` test is failing with `HasCycle(map[a:[b] b:[c] c:[d] d:[e] e:[c]]) = false, want true`\n\nThe second failure reveals the core issue: when a node like \"e\" points to \"c\", and \"c\" points to \"d\", etc., forming a cycle `c -> d -> e -> c`, my algorithm isn't detecting it properly.\n\nThe problem is that I'm only checking nodes that exist as keys in the graph, but I need to handle the case where a node might not be a key in the map (has no outgoing edges) but could still be part of a cycle path.\n\nLooking more closely at the `cycle_deep_in_chain` example:\n- `map[a:[b] b:[c] c:[d] d:[e] e:[c]]`\n- This forms a cycle: `c -> d -> e -> c`\n\nThe issue is that my DFS state tracking isn't working correctly. Let me trace through:\n1. Start at \"a\", mark as visiting (1)\n2. Go to \"b\", mark as visiting (1)  \n3. Go to \"c\", mark as visiting (1)\n4. Go to \"d\", mark as visiting (1)\n5. Go to \"e\", mark as visiting (1)\n6. From \"e\" go to \"c\" - \"c\" is already in state 1 (visiting), so should return true\n\nWait, that should work. Let me re-examine the logic.\n\nActually, I think the issue might be with how I'm handling nodes that aren't keys in the graph. But in this case, all nodes in the cycle are keys.\n\nLet me check the duplicate edges test - it probably has something like `map[a:[b,b]]` or similar, which shouldn't affect cycle detection but might expose an issue.\n\nThe real problem is likely that I'm checking `if _, exists := state[node]; !exists` when I should be checking if the node exists in the graph map instead. Let me fix this:\n\n```go\npackage challenge\n\nfunc HasCycle(graph map[string][]string) bool {\n\tif graph == nil || len(graph) == 0 {\n\t\treturn false\n\t}\n\n\t// States: 0 = unvisited, 1 = visiting (in current DFS path), 2 = visited (completed)\n\tstate := make(map[string]int)\n\n\tvar dfs func(node string) bool\n\tdfs = func(node string) bool {\n\t\t// If node is not in the graph, it has no outgoing edges, so no cycle from here\n\t\tif _, exists := graph[node]; !exists {\n\t\t\treturn false\n\t\t}\n\n\t\t// If we've already finished processing this node, no cycle through it\n\t\tif state[node] == 2 {\n\t\t\treturn false\n\t\t}\n\n\t\t// If we're currently visiting this node, we found a cycle\n\t\tif state[node] == 1 {\n\t\t\treturn true\n\t\t}\n\n\t\t// Mark as visiting\n\t\tstate[node] = 1\n\n\t\t// Visit all neighbors\n\t\tfor _, neighbor := range graph[node] {\n\t\t\tif dfs(neighbor) {\n\t\t\t\treturn true\n\t\t\t}\n\t\t}\n\n\t\t// Mark as fully visited\n\t\tstate[node] = 2\n\t\treturn false\n\t}\n\n\t// Check each node in the graph for cycles\n\tfor node := range graph {\n\t\tif state[node] == 0 { // Unvisited\n\t\t\tif dfs(node) {\n\t\t\t\treturn true\n\t\t\t}\n\t\t}\n\t}\n\n\treturn false\n}\n```",
    "passed": 1,
    "test_error": ""
  }
]