# Golang BFS topological sort

• IMO it's difficult to solve this for the first time unless you know the concept of topological sort.
In BFS manner,

``````1. We store how many incoming nodes exist per node on graph
2. Every time we find the node in BFS, we decrement the number of incoming node.
3. If and only if the number becomes 0, we add the node to the queue and process further.
``````

After queue becomes empty, we need to check if visited number equals to a number of courses. If not, it means we have a cycle in the graph.

``````func findOrder(numCourses int, prerequisites [][]int) []int {
graph, incomings := buildMap(numCourses, prerequisites)

var starts []int
for i, incoming := range incomings {
if incoming == 0 {
starts = append(starts, i)
}
}

var res []int
var visitNum int
for _, start := range starts {
queue := []int{start}
res = append(res, start)
visitNum += 1
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
neighbors, ok := graph[node]
if ok {
for _, neighbor := range neighbors {
incomings[neighbor] -= 1
if incomings[neighbor] == 0 {
queue = append(queue, neighbor)
res = append(res, neighbor)
visitNum += 1
}
}
}
}
}
if visitNum == numCourses {
return res
}
return []int{}
}

func buildMap(numCourses int, prerequisites [][]int) (map[int][]int, []int) {
graph := make(map[int][]int)
incomings := make([]int, numCourses)
for _, preq := range prerequisites {
if _, ok := graph[preq[1]]; !ok {
graph[preq[1]] = []int{preq[0]}
} else {
graph[preq[1]] = append(graph[preq[1]], preq[0])
}
incomings[preq[0]] += 1
}
return graph, incomings
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.