Go Coding with Asparagos: Will Graph Cycles Spoil the Salsa Festival?

#go #programming #humor #algorithms

Salsa Festival! All vegetables are invited! Can cycles ruin the fun?

Hi! I'm Asparagos - an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem of Salsa Festival 🥗.

Problem

There’s a salsa festival in the Veggie Kingdom this weekend. All vegetables are invited, free of charge!

But veggies are picky: each one will only come if certain friends arrive first.
For example, bell pepper will only show up after his brother, chili pepper. A potato will only come if both pumpkin and corn are already there (this trio became best friends after the lecture "Introduction to the Carbohydrate Diet").

Nobody can untangle these complicated relationships. Did you know that apple is trying to sue pineapple for using its name?

So, can we figure out whether all the veggies will come to the salsa festival?

Input 🥒

vegNum int - the total number of vegetables in the kingdom.

requirements [][]int - each element requirements[i] = [a, b] means that vegetable a will come to the festival only if vegetable b comes first.

Output 🍅

true if it’s possible for all vegetables to attend the festival,

false if some requirements create a deadlock (i.e. a cycle).

Examples 🌶️:

Example 1

Input: vegNum = 2, requirements = [[1, 0]]

Output: true

Vegetable 0 can come without any conditions. Vegetable 1 depends on 0, and since 0 can come, 1 can come too.
Example 2

Input: vegNum = 2, requirements = [[1, 0], [0, 1]]

Output: false

Vegetable 1 depends on 0, and 0 depends on 1. This creates a cycle, neither can come first, so no one comes.

Solution 💡

We start by building a graph of vegetables. Each vertex represents a vegetable. An edge a -> b means that b will only come if a comes first. Now the problem reduces to detecting a cycle in this graph, which we can do using Depth-First Search (DFS).
The dfs function is a recursive function with the following arguments:

graph [][]int - the adjacency list of the vegetable graph

vertex int – the current node we are traversing

pathVertices map[int]bool - tracks nodes on the current DFS path (used to detect a cycle)

visited map[int]bool - tracks all previously visited nodes (used to avoid duplicate traversal)

It returns true if a cycle is found, and false otherwise.
Cycle detection logic:

If the vertex is already in pathVertices, that means we've visited it in the current path — a cycle is found, so we return true.

If it's already in visited but not in the current path, we've checked it before and know it doesn’t lead to a cycle — return false.
Otherwise, we:

Mark the current node as visited (both in visited and pathVertices).

Recursively apply DFS to its children.

After processing all descendants, remove the current node from pathVertices (as we’re backtracking).

If no cycles are found during any DFS traversal, return true. Otherwise, return false.

func canAllVeggiesCome(vegNum int, requirements [][]int) bool {
    vegGraph := make([][]int, vegNum)
    for _, req := range requirements {
        toVeg := req[0]
        fromVeg := req[1]
        vegGraph[fromVeg] = append(vegGraph[fromVeg], toVeg)
    }

    visited := make(map[int]bool)
    for veg := 0; veg < vegNum; veg++ {
        if visited[veg] {
            continue
        }
        pathVertices := make(map[int]bool)
        if dfs(vegGraph, veg, pathVertices, visited) {
            return false
        }
    }
    return true
}

func dfs(graph [][]int, vertex int, pathVertices map[int]bool, visited map[int]bool) bool {
    if pathVertices[vertex] {
        return true
    }
    if visited[vertex] {
        return false
    }
    pathVertices[vertex] = true
    visited[vertex] = true
    for _, childV := range graph[vertex] {
        if dfs(graph, childV, pathVertices, visited) {
            return true
        }
    }
    pathVertices[vertex] = false
    return false
}