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

题目

题目链接：
https://www.nowcoder.com/practice/64a4c026b2aa4411984f560deec36323

思路

图，BFS，队列
1

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numProject int整型
     * @param groups int整型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<>();
        }
    }
}
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

参考答案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  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
76

参考答案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 = [];
    }

}

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
81
82
83
84
85
86
87
88