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 path), 2 = visited (done)
	state := make(map[string]int)

	// Initialize all nodes present as keys
	for node := range graph {
		state[node] = 0
	}

	var dfs func(string) bool
	dfs = func(node string) bool {
		// If currently visiting this node, we found a cycle
		if state[node] == 1 {
			return true
		}
		// If already fully processed, no cycle via this path
		if state[node] == 2 {
			return false
		}

		// Mark as currently visiting
		state[node] = 1

		// Explore neighbors
		for _, neighbor := range graph[node] {
			// Ensure neighbor is tracked (may not be a key in graph)
			if _, exists := state[neighbor]; !exists {
				state[neighbor] = 0
			}
			if dfs(neighbor) {
				return true
			}
		}

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

	// Run DFS from each unvisited node
	for node := range graph {
		if state[node] == 0 {
			if dfs(node) {
				return true
			}
		}
	}

	return false
}
```

The user wants a Go function `HasCycle` that detects cycles in a directed graph represented as an adjacency map.

Key requirements:
1. Input: `graph map[string][]string`
2. Output: `bool` (true if cycle exists, false otherwise)
3. Self-loops count as cycles
4. Nodes referenced as neighbors but not as keys are valid nodes with no outgoing edges
5. Empty/nil map → false
6. Duplicate edges should not break detection

Algorithm:
I'll use DFS with three states for each node:
- 0: unvisited
- 1: visiting (currently in the recursion stack)
- 2: visited (fully processed)

If we encounter a node with state 1 during DFS, we've found a cycle.

Steps:
1. Handle nil/empty graph
2. Create a state map for all nodes
3. For each unvisited node, start DFS
4. In DFS:
   - Mark current node as "visiting"
   - For each neighbor:
     - If neighbor is "visiting", return true (cycle found)
     - If neighbor is "unvisited", recursively check
   - Mark current node as "visited"
   - Return false

Let me implement this:

```go
package challenge

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

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

    // Initialize all nodes in the graph as unvisited
    for node := range graph {
        state[node] = 0
    }

    var dfs func(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 through this path
        if state[node] == 2 {
            return false
        }

        // Mark as visiting
        state[node] = 1

        // Visit all neighbors
        for _, neighbor := range graph[node] {
            // Initialize neighbor state if not seen before
            if _, exists := state[neighbor]; !exists {
                state[neighbor] = 0
            }
            if dfs(neighbor) {
                return true
            }
        }

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

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

    return false
}
```

Wait, I need to be careful. The graph map only contains keys for nodes that have outgoing edges. But neighbors might not be keys. My code handles this by initializing state for neighbors when encountered.

Let me trace through the examples:

1. `{"a": {"b"}, "b": {"c"}, "c": {}}`
   - Start DFS from "a": state["a"] = 1
   - Visit "b": state["b"] = 1
   - Visit "c": state["c"] = 1
   - "c" has no neighbors, state["c"] = 2
   - Back to "b", state["b"] = 2
   - Back to "a", state["a"] = 2
   - No cycle found → false ✓

2. `{"a": {"a"}}`
   - Start DFS from "a": state["a"] = 1
   - Visit "a": state["a"] == 1, return true ✓

3. `{"a": {"b"}, "b": {"c"}, "c": {"a"}}`
   - Start DFS from "a": state["a"] = 1
   - Visit "b": state["b"] = 1
   - Visit "c": state["c"] = 1
   - Visit "a": state["a"] == 1, return true ✓

4. `{}`
   - Empty map, return false ✓

This looks correct. Let me finalize the solution.