Topological Sort (Kahn's Algorithm)

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {

}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }

    // Nodes with no dependencies can go first.
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }

    // Nodes with no dependencies can go first.
    queue := []int{}
    for v := 0; v < n; v++ {
        if indeg[v] == 0 {
            queue = append(queue, v)
        }
    }
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }

    // Nodes with no dependencies can go first.
    queue := []int{}
    for v := 0; v < n; v++ {
        if indeg[v] == 0 {
            queue = append(queue, v)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
    }
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }

    // Nodes with no dependencies can go first.
    queue := []int{}
    for v := 0; v < n; v++ {
        if indeg[v] == 0 {
            queue = append(queue, v)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        // Removing node "frees" its dependents.
    }
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }

    // Nodes with no dependencies can go first.
    queue := []int{}
    for v := 0; v < n; v++ {
        if indeg[v] == 0 {
            queue = append(queue, v)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        // Removing node "frees" its dependents.
        for _, next := range graph[node] {
            indeg[next]--
            if indeg[next] == 0 {
                queue = append(queue, next)
            }
        }
    }
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }

    // Nodes with no dependencies can go first.
    queue := []int{}
    for v := 0; v < n; v++ {
        if indeg[v] == 0 {
            queue = append(queue, v)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        // Removing node "frees" its dependents.
        for _, next := range graph[node] {
            indeg[next]--
            if indeg[next] == 0 {
                queue = append(queue, next)
            }
        }
    }

    // Fewer than n nodes ordered means there was a cycle.
}

// graph is a DAG adjacency list: an edge u -> v means u must come before v.
func topoSort(graph [][]int) []int {
    // Micropattern: count incoming edges for every node.
    n := len(graph)
    indeg := make([]int, n)
    for _, edges := range graph {
        for _, v := range edges {
            indeg[v]++
        }
    }

    // Nodes with no dependencies can go first.
    queue := []int{}
    for v := 0; v < n; v++ {
        if indeg[v] == 0 {
            queue = append(queue, v)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        // Removing node "frees" its dependents.
        for _, next := range graph[node] {
            indeg[next]--
            if indeg[next] == 0 {
                queue = append(queue, next)
            }
        }
    }

    // Fewer than n nodes ordered means there was a cycle.
    if len(order) != n {
        return nil
    }
    return order // O(V + E)
}