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

题目

题目链接：
https://www.nowcoder.com/practice/1a16c1b2d2674e1fb62ce8439e867f33

核心

图，BFS,拓扑排序，队列
1

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numProject int整型 
     * @param groups int整型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<>();
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

参考答案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  int
	in    int
	nexts []*GNode
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

参考答案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 = [];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80