牛客NC314 体育课测验(一)【中等图，BFS，拓扑排序 Java，Go、PHP】

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

题目

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

核心

图，BFS,拓扑排序，队列

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型ArrayList<ArrayList<>> * @return bool布尔型*/public boolean canFinish (int numProject, ArrayList<ArrayList<Integer>> groups) {//图，bfs,拓扑排序Map<Integer,GNode> graph = new HashMap<>();for (int i = 0; i <numProject ; i++) {graph.put(i,new GNode(i));}for (ArrayList<Integer> group : groups) {int vf = group.get(1);int tf = group.get(0);GNode fn = graph.get(vf);GNode tn = graph.get(tf);fn.nexts.add(tn);tn.in++;}Queue<GNode> q0 = new LinkedList<>();Set<Integer> visited = new HashSet<>();for(int k: graph.keySet()){if(graph.get(k).in==0){q0.add(graph.get(k));visited.add(graph.get(k).data);}}List<Integer> ll = new ArrayList<>();while (!q0.isEmpty()){int size = q0.size();for (int i = 0; i <size ; i++) {GNode pop = q0.poll();ll.add(pop.data);for (GNode next : pop.nexts) {if(--next.in==0){if(visited.contains(next.data)) return false; //出现环了q0.add(next);visited.add(next.data);}}}}return ll.size()  == numProject? true: false;}static class GNode{int data;int in;List<GNode> nexts;public GNode(int d){data =d;in =0;nexts = new ArrayList<>();}}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型二维数组 * @return bool布尔型
*/
func canFinish( numProject int ,  groups [][]int ) bool {//bfs,图，拓扑排序graph := map[int]*GNode{} //图for i := 0; i < numProject; i++ {graph[i] = &GNode{i, 0, []*GNode{}}}for _, v := range groups {vf := v[1]vt := v[0]nodef := graph[vf]nodet := graph[vt]nodet.in++nodef.nexts = append(nodef.nexts, nodet)}q0 := []*GNode{} //队列visted := map[int]bool{}for _, node := range graph {if node.in == 0 {q0 = append(q0, node)visted[node.data] = true}}ll := []int{}for len(q0) > 0 {size := len(q0)q0bak := []*GNode{}for i := 0; i < size; i++ {pop := q0[i]ll = append(ll, pop.data)for _, next := range pop.nexts {next.in--if next.in == 0 {_, ok := visted[next.data]if ok {return false //出现环了}q0bak = append(q0bak, next)visted[next.data] = true}}}q0 = q0bak}if len(ll) == numProject {return true}return false
}type GNode struct {data  intin    intnexts []*GNode
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型二维数组 * @return bool布尔型*/
function canFinish( $numProject ,  $groups )
{//bfs, 图，拓扑排序$graph = [];for($i=0;$i<$numProject;$i++){$graph[$i] = new Node($i);}foreach ($groups as $v){$fv = $v[1];$tv = $v[0];$nodef = $graph[$fv];$nodet = $graph[$tv];$nodet->in++;$nodef->nexts[count($nodef->nexts)] = $nodet;}$q0 = [];$visited = [];foreach ($graph as $cur){if($cur->in ==0){$q0[count($q0)] = $cur;$visited[$cur->data] = true;}}$ll = [];while (count($q0) >0){$size = count($q0);$q0bak = [];for($i=0;$i<$size;$i++){$pop = $q0[$i];$ll[count($ll)] = $pop->data;foreach ($pop->nexts as $next){$next->in--;if($next->in ==0){if(isset($visited[$next->data])){return false; //出现环了}$q0bak[count($q0bak)] = $next;$visited[$next->data] =true;}}}$q0 =$q0bak;}return count($ll) ==$numProject? true:false;
}class Node{public $data;public $in;public $nexts;public function __construct($d){$this->data=$d;$this->in =0;$this->nexts = [];}
}