体育课共有个考核项目,编号为到,考核中每两个项目被划分为一组得到分组数组,现规定若想完成项目,必须先完成。保证所有分组互不相同,若分组情况能顺利完成考核,请返回任意的一个完成顺序,否则返回空数组 。
数据范围:
3,[[2,1]]
[1,2,0]
要先完成1号项目,再完成2号项目,而0号项目不受约束,故可以以1 2 0的顺序完成项目。
3,[[1,0], [0,1]]
[]
第一个分组要求先完成0号项目,再完成1号项目;而第二个分组要求先完成1号项目,再完成0号项目,自相矛盾,故不可以完成项目。
public ArrayList<Integer> findOrder(int numProject, ArrayList<ArrayList<Integer>> groups) { // 使用邻接表表示图 ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(); for (int i = 0; i < numProject; i++) { adjList.add(new ArrayList<>()); } // 入度数组 int[] indegree = new int[numProject]; // 构建图 for (ArrayList<Integer> group : groups) { int first = group.get(0); int second = group.get(1); adjList.get(second).add(first); indegree[first]++; } // 用于存储入度为零的节点的队列 Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < numProject; i++) { if (indegree[i] == 0) { queue.offer(i); } } // 结果列表,用于存储项目的完成顺序 ArrayList<Integer> result = new ArrayList<>(); // 处理队列 /** * 公共节点的每个前驱节点度为1,在最后一个前驱节点处理完成时, * 公共节点的度降为0,继续处理公共节点的后继节点,公共节点的后继节点度为1, * 确保减1操作后度降为0,能正确加入队列,继续处理 */ while (!queue.isEmpty()) { int current = queue.poll(); result.add(current); for (int neighbor : adjList.get(current)) { indegree[neighbor]--; if (indegree[neighbor] == 0) { queue.offer(neighbor); } } } return result.size() == numProject ? result : new ArrayList<>(); // 如果存在循环或未处理所有节点,则返回空列表 }