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-02T23:52:45.743269166+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-02T23:52:45.743270136+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/duplicate_edges_forming_cycle\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T23:52:45.743271006+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/long_chain_no_cycle\"}\n{\"Time\":\"2026-07-02T23:52:45.743271786+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/long_chain_no_cycle\",\"Output\":\"=== RUN   TestHasCycle/long_chain_no_cycle\\n\"}\n{\"Time\":\"2026-07-02T23:52:45.743272886+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-02T23:52:45.743274806+02:00\",\"Action\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/long_chain_no_cycle\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T23:52:45.743275686+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\"}\n{\"Time\":\"2026-07-02T23:52:45.743276436+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\",\"Output\":\"=== RUN   TestHasCycle/cycle_deep_in_chain\\n\"}\n{\"Time\":\"2026-07-02T23:52:45.743277406+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-02T23:52:45.743278586+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-02T23:52:45.743279576+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle/cycle_deep_in_chain\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T23:52:45.743280836+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle\",\"Output\":\"--- FAIL: TestHasCycle (0.00s)\\n\"}\n{\"Time\":\"2026-07-02T23:52:45.743281836+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestHasCycle\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T23:52:45.743282946+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\n\"}\n{\"Time\":\"2026-07-02T23:52:45.743384107+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge\\t0.001s\\n\"}\n{\"Time\":\"2026-07-02T23:52:45.743394617+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0.001}"
  },
  {
    "total": 1,
    "answer": "Looking at the test failures, I can see two issues:\n\n1. `duplicate_edges_forming_cycle` - The test expects a cycle to be detected when there are duplicate edges forming a cycle, but my implementation might not be handling this correctly.\n\n2. `cycle_deep_in_chain` - For the graph `map[a:[b] b:[c] c:[d] d:[e] e:[c]]`, there's clearly a cycle `c -> d -> e -> c`, but my function returns `false`.\n\nThe problem is likely that I'm only checking nodes that are keys in the graph, but I need to also consider nodes that appear as neighbors but aren't keys (which should be treated as having no outgoing edges). However, looking more carefully at the second failing test, the issue is that my DFS isn't properly detecting cycles when we revisit a node that's currently in the recursion stack.\n\nLet me trace through `map[a:[b] b:[c] c:[d] d:[e] e:[c]]`:\n- Start DFS at 'a': a -> b -> c -> d -> e\n- At 'e', neighbors are ['c']\n- When we visit 'c' again from 'e', 'c' should be in state 1 (visiting) since the path is a->b->c->d->e->c\n\nThe issue might be that I'm not handling nodes that aren't keys in the graph properly. 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 as a key, it has no outgoing edges\n\t\tneighbors, exists := graph[node]\n\t\tif !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 neighbors {\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": ""
  }
]