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 {
	// Track node states: 0 = unvisited, 1 = visiting, 2 = visited
	state := make(map[string]int)

	// Helper DFS function to detect cycles
	var dfs func(node string) bool
	dfs = func(node string) bool {
		// If node is currently being visited, we found a cycle
		if state[node] == 1 {
			return true
		}

		// If node is already fully visited, no cycle from this path
		if state[node] == 2 {
			return false
		}

		// Mark node as being visited
		state[node] = 1

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

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

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

	return false
}
```

The task is to implement a cycle detection algorithm for a directed graph in Go. The graph is represented as an adjacency map where each key is a node and its value is a slice of nodes it has directed edges to.

To detect cycles in a directed graph, I can use Depth First Search (DFS) with three states for each node:
1. **Unvisited** - Node has not been visited yet
2. **Visiting** - Node is currently being processed (in the current DFS path)
3. **Visited** - Node has been completely processed

If during DFS we encounter a node that is in the "Visiting" state, we've found a cycle.

Here's my approach:
1. Track visited nodes with three states
2. For each unvisited node in the graph, start a DFS
3. During DFS, if we encounter a node that's currently being visited, we have a cycle
4. If we complete DFS for a node without finding a cycle, mark it as fully visited

Let me implement this:

```go
package challenge

func HasCycle(graph map[string][]string) bool {
    // Track node states: 0 = unvisited, 1 = visiting, 2 = visited
    state := make(map[string]int)
    
    // Helper DFS function
    var dfs func(node string) bool
    dfs = func(node string) bool {
        // If node is currently being visited, we found a cycle
        if state[node] == 1 {
            return true
        }
        
        // If node is already fully visited, no cycle from this path
        if state[node] == 2 {
            return false
        }
        
        // Mark node as being visited
        state[node] = 1
        
        // Visit all neighbors
        for _, neighbor := range graph[node] {
            if dfs(neighbor) {
                return true
            }
        }
        
        // Mark node as fully visited
        state[node] = 2
        return false
    }
    
    // Check all nodes in the graph
    for node := range graph {
        if state[node] == 0 {
            if dfs(node) {
                return true
            }
        }
    }
    
    return false
}
```

I need to handle nodes that appear as neighbors but aren't keys in the graph. These nodes have no outgoing edges, so they won't cause cycles. My current implementation handles this correctly since `graph[neighbor]` will return an empty slice for such nodes.

However, I should also consider nodes that are only reachable through traversal but never appear as keys. Since I'm iterating over all keys in the graph, I'll catch cycles starting from any node that has outgoing edges.

Let me trace through the examples to verify:

Example 1: `{"a": {"b"}, "b": {"c"}, "c": {}}`
- Start at "a", mark as visiting
- Visit "b", mark as visiting
- Visit "c", mark as visiting
- "c" has no neighbors, mark as visited
- Backtrack to "b", mark as visited
- Backtrack to "a", mark as visited
- No cycle found → false ✓

Example 2: `{"a": {"a"}}`
- Start at "a", mark as visiting
- Visit "a" (neighbor), it's already visiting → cycle found → true ✓

Example 3: `{"a": {"b"}, "b": {"c"}, "c": {"a"}}`
- Start at "a", mark as visiting
- Visit "b", mark as visiting
- Visit "c", mark as visiting
- Visit "a" (neighbor), it's already visiting → cycle found → true ✓

Example 4: `{}`
- No nodes to iterate → false ✓

The implementation handles all cases correctly. I should also consider edge cases like nil maps, which my code handles since iterating over a nil map does nothing.

One thing to verify: when accessing `graph[node]` for a node that's not a key, Go returns an empty slice, which is safe. This means nodes that only appear as neighbors but not as keys will have no outgoing edges, which is correct.

I'm ready to write the final solution.