每日OJ_牛客_NC316体育课测验(二)_拓扑排序_C++_Java

目录

牛客_NC316体育课测验(二)_拓扑排序

题目解析

C++代码

Java代码

---

牛客_NC316体育课测验(二)_拓扑排序

体育课测验(二)_牛客题霸_牛客网

描述：

        体育课共有numProjectnumProject个考核项目，编号为00到numProject−1numProject−1，考核中每两个项目被划分为一组得到分组数组groupsigroupsi​，现规定若想完成项目groupsi[0]groupsi​[0]，必须先完成groupsi[1]groupsi​[1]。保证所有分组互不相同，若分组情况能顺利完成考核，请返回任意的一个完成顺序,否则返回空数组 。

数据范围：

1≤numProject≤2000 1≤groupsi.length≤numProject∗(numProject−1)

---

题目解析

拓扑排序类型题：

起始时，将所有入度为 0 的节点进行入队（入度为 0，说明没有边指向这些节点，将它们放到拓扑排序的首部，不会违反拓扑序定义）。从队列中进行节点出队操作，出队序列就是对应我们输出的拓扑序。对于当前弹出的节点 x，遍历x 的所有出度y，即遍历所有由 x直接指向的节点y，对y做入度减一操作（因为x节点已经从队列中弹出，被添加到拓扑序中，等价于x节点从有向图中被移除，相应的由x发出的边也应当被删除，带来的影响是与 x相连的节点y的入度减一）。对y进行入度减一之后，检查 y的入度是否为0，如果为0则将y入队（当y的入度为0，说明有向图中在y前面的所有的节点均被添加到拓扑序中，此时 可以作为拓扑序的某个片段的首部被添加，而不是违反拓扑序的定义）。循环流程 2、3 直到队列为空。 C++代码 class Solution { public: vector<int> findOrder(int numProject, vector<vector<int> >& groups) { vector<vector<int>> edg(numProject); vector<int> in(numProject); for(auto& e : groups) { int a = e[0], b = e[1]; edg[b].push_back(a); // b->a in[a]++; } queue<int> q; for(int i = 0; i < numProject; ++i) { if(in[i] == 0) q.push(i); } vector<int> ret; while(q.size()) { int x = q.front(); q.pop(); ret.push_back(x); for(auto& e : edg[x]) { if(--in[e] == 0) q.push(e); } } // if(ret.size() == numProject) // return ret; // return {}; return ret.size()== numProject ? ret : (ret.clear(), ret); } }; Java代码 import java.util.*; public class Solution { public ArrayList<Integer> findOrder (int n, ArrayList<ArrayList<Integer>> groups) { List<List<Integer>> edges = new ArrayList<>(); // 存储边 for(int i = 0; i < n; i++) { edges.add(new ArrayList<>()); } int[] in = new int[n]; // ⼊度 // 1. 建图 for(int i = 0; i < groups.size(); i++) { int a = groups.get(i).get(0), b = groups.get(i).get(1); // b -> a in[a]++; edges.get(b).add(a); } Queue<Integer> q = new LinkedList<>(); // 2. ⼊度为 0 的点加⼊到队列中 for(int i = 0; i < n; i++) { if(in[i] == 0) { q.add(i); } } ArrayList<Integer> ret = new ArrayList<>(); // 3. 拓扑排序（BFS） while(!q.isEmpty()) { int a = q.poll(); ret.add(a); for(int b : edges.get(a)) // a -> b { if(--in[b] == 0) { q.add(b); } } } if(ret.size() == n) return ret; else return new ArrayList<>(); } }