题解 | #牛牛吃水果的顺序#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param numFruits int整型
 * @param prerequisites int整型二维数组
 * @return int整型二维数组
 */
type tuoPu struct {
	in_count int
	val      int
	out      *out
}

type out struct {
	val  int
	next *out
}

var result [][]int

func findFruitOrder(numFruits int, prerequisites [][]int) [][]int {
	// write code here
	result = make([][]int, 0, 100)
	arr := make([]tuoPu, numFruits)
	for i := 0; i < numFruits; i++ {
		arr[i] = tuoPu{val: i}
	}
	for i := 0; i < len(prerequisites); i++ {
		v1 := prerequisites[i][0] //在后
		v2 := prerequisites[i][1] //在前
		arr[v1].in_count++
		if arr[v2].out == nil {
			arr[v2].out = &out{val: v1}
		} else {
			v := arr[v2].out
			for v.next != nil {
				v = v.next
			}
			v.next = &out{val: v1}
		}
	}
	temp := make([]int, numFruits)
	recursion(arr, temp, 0)
	return result
}

func recursion(arr []tuoPu, temp []int, index int) {
	if index >= len(temp) {
		return
	}
	for i := 0; i < len(arr); i++ {
		if arr[i].in_count == 0 {
			temp[index] = arr[i].val
			arr[i].in_count-- //变成-1
			o := arr[i].out   //遍历出度
			for o != nil {
				arr[o.val].in_count-- //出度减一
				o = o.next
			}
			recursion(arr, temp, index+1)
			arr[i].in_count++
			o = arr[i].out
			for o != nil {
				arr[o.val].in_count++ //出度加一
				o = o.next
			}
		}
	}
	if index == len(temp)-1 {
		//v := temp
		v := make([]int, len(temp))
		for i := 0; i < len(temp); i++ {
			v[i] = temp[i]
		}
		result = append(result, v)
	}
}