a**x
发帖数: 14 | 1 class Solution {
public:
bool canFinish(int numCourses, vector>& prerequisites) {
// 0..n-1
vector vis(numCourses, false);
vector > mp(numCourses, vector());
vector ind(numCourses);
// init the map
for (int i = 0; i < prerequisites.size(); i++) {
int x = prerequisites[i][0];
int y = prerequisites[i][1];
mp[x].push_back(y);
ind[y]++;
}
queue阅读全帖 |
|
c*******e
发帖数: 373 | 2 看题目，应该是传说中的拓扑排序，自己琢磨了一下逻辑，然后Google “拓扑排序”
，发现我的思路就是标准拓扑排序的思路，把没有依赖的都输出了，把剩下依赖它的“
依赖”去掉，直到全部输出，或者，找不到没有依赖的（那就是有循环）为止。下面代
码已提交、接受
有些同学提到深度优先、广度优先，我不太明白是怎么回事？
class Node {
int id; // My course ID
int numOfPre; // How many prerequisites do I have
HashSet preOf; // How many courses have me as prerequisite?
Node(int id){this.id = id; numOfPre = 0; preOf = new HashSet()
;}
void addDependant(Node n){if (!preOf.contains(n)) /*Input ... 阅读全帖 |
|
d******4
发帖数: 132 | 3 欢迎各位大牛批评指导。统计背景，正在刷题，希望得到cs专家的指导。
class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {integer[]}
def findOrder(self, numCourses, prerequisites):
if not prerequisites:
return range(numCourses)
dict={}
for e in prerequisites:
if e[0] not in dict:
dict[e[0]] = [e[1]]
else:
if e[1] not in dict[e[0]]:
dict[e[0]].append(e[1])
... 阅读全帖 |
|
n**e
发帖数: 116 | 4 public class Solution {
private final Map> adj = new HashMap<>();
public boolean canFinish(int numCourses, int[][] prerequisites) {
for (int i = 0; i < prerequisites.length; ++i) {
int u = prerequisites[i][0], v = prerequisites[i][1];
addEdge(u, v);
}
boolean[] visited = new boolean[numCourses];
boolean[] recursionStack = new boolean[numCourses];
for (Integer v : adj.keySet()) {
if (hasCycl... 阅读全帖 |
|
