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
	}

	// State tracking: 0 = unvisited, 1 = visiting (in current recursion stack), 2 = visited
	state := make(map[string]int)

	var dfs func(string) bool
	dfs = func(node string) bool {
		if s, ok := state[node]; ok {
			return s == 1
		}
		state[node] = 1
		for _, neighbor := range graph[node] {
			if dfs(neighbor) {
				return true
			}
		}
		state[node] = 2
		return false
	}

	for node := range graph {
		if _, ok := state[node]; !ok {
			if dfs(node) {
				return true
			}
		}
	}
	return false
}
```

The user wants a Go function `HasCycle` that detects if a directed graph contains a cycle.
The graph is represented as `map[string][]string`.
I need to implement this in `solution.go` inside `package challenge`.

Algorithm for cycle detection in a directed graph:
DFS with three states for each node:
- Unvisited (0)
- Visiting (1) - currently in the recursion stack
- Visited (2) - fully processed

If we encounter a node that is in the "Visiting" state during DFS, we found a cycle.
If we encounter a node that is "Visited", we skip it.
After processing all neighbors of a node, mark it as "Visited".

We need to handle all nodes in the graph. Some nodes might only appear as values (neighbors) but not as keys. The problem says: "A neighbor that does not appear as a key in the map is a valid node with no outgoing edges." So we should collect all unique nodes first, or just iterate over keys and also track visited nodes. Actually, iterating over keys is enough to start DFS, but we might miss nodes that are only targets? Wait, if a node is only a target and has no outgoing edges, it can't be part of a cycle unless it's also a source. But to be safe, we can collect all nodes from keys and values, or just iterate over keys. Actually, cycles must involve nodes that have outgoing edges, so iterating over keys is sufficient. But to be strictly correct, we can just iterate over all keys. If a node is only a value, it has no outgoing edges, so it can't start a cycle. So iterating over keys is fine.

Wait, what if the graph has nodes that are only values? They won't be in keys. They can't be part of a cycle because they have no outgoing edges. So iterating over keys is sufficient.

Let's refine the DFS approach:
```go
func HasCycle(graph map[string][]string) bool {
    if len(graph) == 0 {
        return false
    }
    
    // States: 0 = unvisited, 1 = visiting, 2 = visited
    state := make(map[string]int)
    
    var dfs func(node string) bool
    dfs = func(node string) bool {
        if s, ok := state[node]; ok {
            return s == 1
        }
        state[node] = 1
        for _, neighbor := range graph[node] {
            if dfs(neighbor) {
                return true
            }
        }
        state[node] = 2
        return false
    }
    
    for node := range graph {
        if state[node] == 0 {
            if dfs(node) {
                return true
            }
        }
    }
    return false
}
```

Wait, `graph[node]` might not exist if `node` is only a value? But we only call `dfs` on keys initially. Inside `dfs`, we iterate over `graph[node]`. If `node` is not a key, `graph[node]` will be `nil` or empty slice, which is fine. But we should handle it gracefully. In Go, accessing a missing key in a map returns the zero value, which for `[]string` is `nil`. Iterating over `nil` slice is safe.

Let's test mentally:
`graph = map[string][]string{"a": {"b"}, "b": {"c"}, "c": {}}`
dfs("a") -> state["a"]=1
  neighbor "b" -> dfs("b") -> state["b"]=1
    neighbor "c" -> dfs("c") -> state["c"]=1
      neighbors: nil -> loop doesn't run
      state["c"]=2 -> returns false
    state["b"]=2 -> returns false
  state["a"]=2 -> returns false
Returns false. Correct.

`graph = map[string][]string{"a": {"a"}}`
dfs("a") -> state["a"]=1
  neighbor "a" -> dfs("a") -> state["a"] is 1 -> returns true
Returns true. Correct.

`graph = map[string][]string{"a": {"b"}, "b": {"c"}, "c": {"a"}}`
dfs("a") -> state["a"]=1
  neighbor "b" -> dfs("b") -> state["b"]=1
    neighbor "c" -> dfs("c") -> state["c"]=1
      neighbor "a" -> dfs("a") -> state["a"] is 1 -> returns true
Returns true. Correct.

`graph = map[string][]string{}` -> len is 0, returns false. Correct.

What about duplicate edges? `graph = map[string][]string{"a": {"b", "b"}}`
dfs("a") -> state["a"]=1
  neighbor "b" -> dfs("b") -> state["b"]=1 -> returns false
  neighbor "b" -> dfs("b") -> state["b"] is 2 -> returns false
Returns false. Correct.

One minor point: `state[node] == 0` check in the loop. Since `state` is a map, accessing `state[node]` returns 0 if not present. So `if state[node] == 0` works. But to be explicit, we can use `if _, ok := state[node]; !ok`. Or just `if state[node] == 0`. It's fine.

Wait, should we consider nodes that are only values? The problem says: "A neighbor that does not appear as a key in the map is a valid node with no outgoing edges." This implies they exist in the graph but have no outgoing edges. They can't be part of a cycle. So iterating over keys is sufficient.

But what if the graph has a cycle that involves a node that is not a key? That's impossible because to be in a cycle, a node must have an outgoing edge to another node in the cycle, so it must be a key.

So the algorithm is solid.

Let's write it out carefully.

```go
package challenge

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

	state := make(map[string]int) // 0: unvisited, 1: visiting, 2: visited

	var dfs func(string) bool
	dfs = func(node string) bool {
		if s, ok := state[node]; ok {
			return s == 1
		}
		state[node] = 1
		for _, neighbor := range graph[node] {
			if dfs(neighbor) {
				return true
			}
		}
		state[node] = 2
		return false
	}

	for node := range graph {
		if state[node] == 0 {
			if dfs(node) {
				return true
			}
		}
	}
	return false
}
```

Wait, `state[node] == 0` works because map returns 0 for missing keys. But to be strictly correct and avoid any confusion, I'll use `if _, ok := state[node]; !ok`. Actually, `state[node] == 0` is fine.

One thing: `graph[node]` when `node` is not a key returns `nil`. Iterating over `nil` is safe in Go. So `for _, neighbor := range graph[node]` is safe.

Let's double check constraints and edge cases.
- Self-loop: handled.
- Neighbor not in keys: handled (graph[node] returns nil, loop doesn't run, state becomes 2).
- Empty map: handled.
- Duplicate edges: handled.
- Disconnected components: handled by iterating over all keys.

Is there any case where `graph` has keys but no edges? e.g., `map[string][]string{"a": nil}`. `len(graph)` is 1. `dfs("a")` runs, `graph["a"]` is nil, loop doesn
…[5710 chars elided]…
 initialized with capacity `len(graph)` for slight optimization, but not necessary.
I'll stick to the current version.

Output matches requirements.
Proceeds. 
```go
package challenge

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

	state := make(map[string]int) // 0: unvisited, 1: visiting, 2: visited

	var dfs func(string) bool
	dfs = func(node string) bool {
		if s, ok := state[node]; ok {
			return s == 1
		}
		state[node] = 1
		for _, neighbor := range graph[node] {
			if dfs(neighbor) {
				return true
			}
		}
		state[node] = 2
		return false
	}

	for node := range graph {
		if _, ok := state[node]; !ok {
			if dfs(node) {
				return true
			}
		}
	}
	return false
}
```
Looks good. I will output this. 
All constraints met. No extra text. Fenced code block. Package challenge. Function signature exact. Handles all cases. O(V+E) complexity. Recursive DFS with 3-color marking. Correct. 
Proceeds. 
[Output Generation] -> *Self-Correction/Verification during generation prep*: 
Wait, should I consider that `graph` might contain nodes that are only values? The problem says "A neighbor that does not appear as a key in the map is a valid node with no outgoing edges." This is just clarifying that dangling edges are allowed. It doesn't require us to process them. Our code only iterates over keys, which is correct because cycles must involve nodes with outgoing edges. So it's fine.

One minor point: `graph[node]` inside `dfs` might panic if `graph` is nil? But we check `len(graph) == 0` at the start, so `graph` is not nil when `dfs` is called. Actually, `graph` could be non-nil but empty, but then the loop over `range graph` won't execute, so `dfs` won't be called. So it's safe.

All good.
Output matches. 
Proceeds. 
[Final Check of the Prompt]
"Implement **`solution.go`** in `package challenge` exporting: `func HasCycle(graph map[string][]string) bool`"
Examples match.
Rules match.
Code is ready.
Output matches request.
Done. 
[Output Generation] -> *Proceeds*