2392. Build a Matrix With Conditions
給一個整數k
有兩個矩陣 rowConditions、colConditions
其中rowConditions[i]=[above_i,below_i]
colConditions[i]=[left_i,right_i]
這兩個矩陣包含1~k
請根據上列訊息，建立出一個2-D矩陣
思路:
去遍歷rowConditions、colConditions
並用indegree矩陣紀錄每個node被指入的次數
用一個outnode去紀錄每個node指出些node
接著找出被指入次數為0的node，這些node就是最上/左邊的node
用一個queue去紀錄這些node
去遍歷queue，每遇到一個node就把他放到sorted矩陣
並把它指出的node的indegree扣掉1
如果indegree被扣到剩0，那就放到queue
最後檢查sorted的長度有沒有k，沒有的話代表有出現矛盾
把rowCondtions、colConditions都經過上述操作
就可以得到2個sorted矩陣，
一個是上而下排放著node
一個是由左而右排放著node
就依序填入最後答案就好
golang code :
func toposprt(k int, condition [][]int) (bool, []int) {
indegree := make([]int, k+1)
outnode := make([][]int, k+1)
sorted := make([]int, 0)
for _, val := range condition {
indegree[val[1]]++
outnode[val[0]] = append(outnode[val[0]], val[1])
}
queue := []int{}
for i := 1; i <= k; i++ {
if indegree[i] == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
tmp := queue[0]
sorted = append(sorted, tmp)
queue = queue[1:]
for _, val := range outnode[tmp] {
indegree[val]