牛客 2024 【牛客赛文X】春招冲刺 ONT73 体育课测验(二) 【中等图/拓扑排序 Java,Go,PHP】

本文主要是介绍牛客 2024 【牛客赛文X】春招冲刺 ONT73 体育课测验(二) 【中等图/拓扑排序 Java,Go,PHP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在这里插入图片描述题目链接：
https://www.nowcoder.com/practice/64a4c026b2aa4411984f560deec36323

思路

图，BFS，队列

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param numProject int整型* @param groups int整型ArrayList<ArrayList<>>* @return int整型ArrayList*/public ArrayList<Integer> findOrder (int numProject,ArrayList<ArrayList<Integer>> groups) {//map表示图Map<Integer, Gnode> graph = new HashMap<>();for (int i = 0; i < numProject ; i++) {graph.put(i, new Gnode(i));}for (ArrayList<Integer> group :groups) { //xxxf代表 开始节点  xxxt代表  f的邻居int vf = group.get(1);int vt = group.get(0);Gnode nodef = graph.get(vf);Gnode nodet = graph.get(vt);nodet.in++;nodef.nexts.add(nodet);}Queue<Gnode> q0 = new LinkedList<>();Set<Integer> set = new HashSet<>();for (Integer v : graph.keySet()) {if (graph.get(v).in == 0) {q0.add(graph.get(v));set.add(v);}}ArrayList<Integer> ll = new ArrayList<>();while (!q0.isEmpty()) {int size = q0.size();for (int i = 0; i < size ; i++) {Gnode cur = q0.poll();ll.add(cur.data);for (Gnode next : cur.nexts) {if (set.contains(next.data)) {return new ArrayList<>();//出现环了，直接返回空的ArrayList}if (--next.in == 0) {q0.add(next);set.add(next.data);}}}}return ll.size() == numProject ? ll : new ArrayList<>();}static class Gnode {int in;int data;List<Gnode> nexts;public Gnode(int d) {data = d;in = 0;nexts =  new ArrayList<>();}}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param numProject int整型* @param groups int整型二维数组* @return int整型一维数组*/
func findOrder(numProject int, groups [][]int) []int {// map表示图graph := map[int]*Gnode{}for i := 0; i < numProject; i++ {graph[i] = &Gnode{i, 0, []*Gnode{}}}for _, gp := range groups {vf := gp[1] //出发vt := gp[0] //到达nodef := graph[vf]nodet := graph[vt]nodef.nexts = append(nodef.nexts, nodet) //增加邻居nodet.in++                               //入度+1}q0 := []*Gnode{} //Go中队列用切片来表示set := map[int]bool{}for _, v1 := range graph {if v1.in == 0 {q0 = append(q0, v1)set[v1.data] = true}}ll := []int{}for len(q0) > 0 {size := len(q0)q0bak := []*Gnode{}for i := 0; i < size; i++ {cur := q0[i]//_,ok:=set[cur.data]ll = append(ll, cur.data)for _, next := range cur.nexts {next.in--if next.in == 0 {_, ok := set[next.data]if ok {return []int{}}q0bak = append(q0bak, next)set[next.data] = true}}}q0 = q0bak}if len(ll) == numProject {return ll}return []int{}
}type Gnode struct { //图的节点data  intin    intnexts []*Gnode
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型二维数组 * @return int整型一维数组*/
function findOrder( $numProject ,  $groups )
{// 图用map表示,PHP中数组是万能，数组也是java中的map,set,list$graph = array();for($i=0;$i<$numProject;$i++){$graph[$i] =  new Gnode($i);}foreach ($groups as $v){$vt= $v[0];$vf =$v[1];$nodet = $graph[$vt]; //出发节点$nodef = $graph[$vf]; //到达节点，也就是出发节点的邻居$nodet->in++;array_push( $nodef->nexts,$nodet);}//BFS$q0 = [];$set =[];foreach ($graph as $node){if($node -> in ==0){$q0[count($q0)] = $node; //放进入度为0的队列$set[$node->data] = $node->data; //访问过该节点了}}$ll = [];while (count($q0) >0){$size = count($q0);$q0bak = [];for($i=0;$i<$size;$i++){$cur =$q0[$i];$ll[count($ll)] = $cur->data;foreach ($cur->nexts as $next){$next->in--;if($next->in ==0){if(isset($set[$next->data])){return []; //出现环了}$q0bak[count($q0bak)] = $next;$set[$next->data] = $next->data;}}}$q0 =$q0bak;}if(count($ll) == $numProject){return $ll;}return [];
}class Gnode{public $in;public $data;public $nexts;public function __construct($d){$this->data = $d;$this->in =0;$this->nexts = [];}}