go-03-detect-cycle

1.000

1/1 tests· algorithms

Proposed solution

```go
package challenge

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

	// Three-color marking system:
	// 0 = unvisited
	// 1 = visiting (in current DFS path)
	// 2 = visited (completed)
	colors := make(map[string]int)
	
	// Helper function to perform DFS
	var dfs func(node string) bool
	dfs = func(node string) bool {
		// If node is currently being visited, we found a cycle
		if colors[node] == 1 {
			return true
		}
		
		// If node is already visited, no cycle from here
		if colors[node] == 2 {
			return false
		}
		
		// Mark as visiting
		colors[node] = 1
		
		// Visit all neighbors
		for _, neighbor := range graph[node] {
			if dfs(neighbor) {
				return true
			}
		}
		
		// Mark as visited
		colors[node] = 2
		return false
	}
	
	// Check each node
	for node := range graph {
		if colors[node] == 0 {
			if dfs(node) {
				return true
			}
		}
	}
	
	return false
}
```

Test output (stdout)

ackage":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle"}
{"Time":"2026-06-30T06:25:37.026779943+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Output":"=== RUN   TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle\n"}
{"Time":"2026-06-30T06:25:37.026782153+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Output":"--- PASS: TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle (0.00s)\n"}
{"Time":"2026-06-30T06:25:37.026784913+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/neighbor_not_a_key_(implicit_leaf),_no_cycle","Elapsed":0}
{"Time":"2026-06-30T06:25:37.026785923+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle"}
{"Time":"2026-06-30T06:25:37.026786713+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"=== RUN   TestHasCycle/duplicate_edges,_no_cycle\n"}
{"Time":"2026-06-30T06:25:37.026789423+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Output":"--- PASS: TestHasCycle/duplicate_edges,_no_cycle (0.00s)\n"}
{"Time":"2026-06-30T06:25:37.026790863+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges,_no_cycle","Elapsed":0}
{"Time":"2026-06-30T06:25:37.026791933+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle"}
{"Time":"2026-06-30T06:25:37.026792973+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"=== RUN   TestHasCycle/duplicate_edges_forming_cycle\n"}
{"Time":"2026-06-30T06:25:37.026794303+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Output":"--- PASS: TestHasCycle/duplicate_edges_forming_cycle (0.00s)\n"}
{"Time":"2026-06-30T06:25:37.026795253+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/duplicate_edges_forming_cycle","Elapsed":0}
{"Time":"2026-06-30T06:25:37.026796253+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle"}
{"Time":"2026-06-30T06:25:37.026797023+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"=== RUN   TestHasCycle/long_chain_no_cycle\n"}
{"Time":"2026-06-30T06:25:37.026798143+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Output":"--- PASS: TestHasCycle/long_chain_no_cycle (0.00s)\n"}
{"Time":"2026-06-30T06:25:37.026800313+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/long_chain_no_cycle","Elapsed":0}
{"Time":"2026-06-30T06:25:37.026801223+02:00","Action":"run","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain"}
{"Time":"2026-06-30T06:25:37.026801963+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"=== RUN   TestHasCycle/cycle_deep_in_chain\n"}
{"Time":"2026-06-30T06:25:37.026803033+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Output":"--- PASS: TestHasCycle/cycle_deep_in_chain (0.00s)\n"}
{"Time":"2026-06-30T06:25:37.026804453+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle/cycle_deep_in_chain","Elapsed":0}
{"Time":"2026-06-30T06:25:37.026805583+02:00","Action":"output","Package":"challenge","Test":"TestHasCycle","Output":"--- PASS: TestHasCycle (0.00s)\n"}
{"Time":"2026-06-30T06:25:37.026806903+02:00","Action":"pass","Package":"challenge","Test":"TestHasCycle","Elapsed":0}
{"Time":"2026-06-30T06:25:37.026813583+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-06-30T06:25:37.027019624+02:00","Action":"output","Package":"challenge","Output":"ok  \tchallenge\t0.002s\n"}
{"Time":"2026-06-30T06:25:37.027031594+02:00","Action":"pass","Package":"challenge","Elapsed":0.002}

System prompt

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.