牛客NC218 检测循环依赖【中等 图 Java，Go，PHP】

题目

题目链接：
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中的队列Queue
	q0 := []*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] = true
			ans = 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  int
	in    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();
 }
}