题目

题目链接：
https://www.nowcoder.com/practice/8dc02ad98553432a90affc3a0484910b

思路

图的基本知识要理解，一般用Map来表示
图解决拓扑排序，依赖之类的问题
感觉课程数在这道题里面可以不用，因为没有规定所有课程都得有先修，
所有先修约束里面可能就     没有包含所有课程

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param prerequisites int整型二维数组* @param n int整型* @return int整型一维数组*/public int[] findOrder (int[][] prerequisites, int n) {//map表示图Map<Integer, Node> g = new HashMap<>();for (int[] item : prerequisites) {int fv = item[1];int tv = item[0];if (!g.containsKey(fv))g.put(fv, new Node(fv));if (!g.containsKey(tv))g.put(tv, new Node(tv));Node fn = g.get(fv);Node tn = g.get(tv);fn.nexts.add(tn);tn.in++;}Queue<Node> q0 = new LinkedList<>();for (Node cur : g.values()) {if (cur.in == 0) {q0.add(cur);}}List<Integer> list = new ArrayList<>();int cnt = 0;while (!q0.isEmpty()) {int size = q0.size();for (int i = 0; i < size ; i++) {Node poll = q0.poll();cnt++;if (list.contains(poll.data)) return new int[0];list.add(poll.data);for (Node next : poll.nexts) {if (--next.in == 0) {q0.add(next);}}}}int[] ans = new int[list.size()];for (int i = 0; i < list.size() ; i++) {ans[i] = list.get(i);}return ans;}static class Node {int data;int in = 0;List<Node> nexts = new ArrayList<>();public Node(int d) {data = d;}}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param prerequisites int整型二维数组* @param n int整型* @return int整型一维数组*/
func findOrder(prerequisites [][]int, n int) []int {//map 模拟图g := map[int]*GNode{}for _, v := range prerequisites {fv := v[1]tv := v[0]_, okf := g[fv]if !okf {g[fv] = CreateGnode(fv)}_, okt := g[tv]if !okt {g[tv] = CreateGnode(tv)}fn := g[fv]tn := g[tv]fn.nexts = append(fn.nexts, tn)tn.in++}//Go中用切片模拟Java中的队列Queueq0 := []*GNode{} //每次进入队列的都是入度为0的for _, cur := range g {if cur.in == 0 {q0 = append(q0, cur)}}set := map[int]bool{}ans := []int{}for len(q0) > 0 {size := len(q0)q0bak := []*GNode{}for i := 0; i < size; i++ {poll := q0[i]_, exist := set[poll.data]if exist {return []int{}}set[poll.data] = trueans = append(ans, poll.data)for _, next := range poll.nexts {next.in--if next.in == 0 {q0bak = append(q0bak, next)}}}q0 = q0bak}return ans
}type GNode struct { //图节点的定义data  intin    int      //入度nexts []*GNode // 图的邻居有哪些
}func CreateGnode(d int) *GNode { //新建节点return &GNode{d, 0, []*GNode{}}
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param prerequisites int整型二维数组 * @param n int整型 * @return int整型一维数组*/
function findOrder( $prerequisites ,  $n )
{//图$map =array();foreach ($prerequisites as $v){$fv = $v[1];$tv = $v[0];if(!isset($map[$fv]))$map[$fv] = new Node($fv);if(!isset($map[$tv]))$map[$tv] = new Node($tv);$fv = $map[$fv];$tn = $map[$tv];array_push($fv->nexts,$tn);$tn->in++;}//队列，PHP中的数组也是队列$q0 = array();foreach ($map as $cur){if($cur->in ==0)array_push($q0,$cur);}$ans = array();while (count($q0) >0){$size = count($q0);for($i=0;$i<$size;$i++){$poll = array_shift($q0);if(in_array($poll->data,$ans)) return array();array_push($ans,$poll->data);foreach ($poll->nexts as $next){$next->in--;if($next->in ==0){array_push($q0,$next);}}}}return $ans;
}class Node{ //图public $data;public $in;public $nexts;public function Node($d){$this->data = $d;$this->in =0;$this->nexts =array();}
}