唉，买个好用的发箍（hair band）真是难啊！# Fashion - 美丽时尚
c*e
1 楼
看题目，应该是传说中的拓扑排序，自己琢磨了一下逻辑，然后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 has repeat
!*/ {preOf.add(n); n.numOfPre ++;}}
}
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
HashMap noPre = new HashMap();
int[][] p = prerequisites;
Node[] all = new Node[numCourses];
// Every course has no prerequisites by default
for (int i = 0; i < numCourses; i ++) {
all[i] = new Node(i);
noPre.put(i, all[i]);
}
// For each a depends on b
for (int i = 0; i < p.length; i ++) {
int a = p[i][0], b = p[i][1];
all[b].addDependant(all[a]);// Record a as b's dependant
noPre.remove(a); // a has prerequisites, so need
remove from the hash map
}
int[] result = new int[numCourses];
int index = 0;
// Output and remove each node in "noPre" since they are all
independant
while (!noPre.isEmpty()) {
Object[] allNoPre = noPre.values().toArray(); // toArray to
avoid iterator on a changing hash map (which is undefined behavior)
noPre.clear();
for (int i = 0; i < allNoPre.length; i++) {
Node n = (Node)allNoPre[i];
result[index] = n.id; index ++;
Object[] allPreOf = n.preOf.toArray();
for (int j = 0; j < allPreOf.length; j ++) {
Node dp = (Node)allPreOf[j];
// Each of n's dependants now has one less prerequisite,
and potentially becomes free (no prerequisites)
if ( (-- dp.numOfPre) == 0)
noPre.put(dp.id, dp);
}
}
}
if (index < numCourses) return new int[0];// Some courses not output
yet, but "noPre" is empty, fail
else return result; // All courses in result,
success
}
}
，发现我的思路就是标准拓扑排序的思路，把没有依赖的都输出了，把剩下依赖它的“
依赖”去掉，直到全部输出，或者，找不到没有依赖的（那就是有循环）为止。下面代
码已提交、接受
有些同学提到深度优先、广度优先，我不太明白是怎么回事？
class Node {
int id; // My course ID
int numOfPre; // How many prerequisites do I have
HashSet
Node(int id){this.id = id; numOfPre = 0; preOf = new HashSet
;}
void addDependant(Node n){if (!preOf.contains(n)) /*Input has repeat
!*/ {preOf.add(n); n.numOfPre ++;}}
}
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
HashMap
int[][] p = prerequisites;
Node[] all = new Node[numCourses];
// Every course has no prerequisites by default
for (int i = 0; i < numCourses; i ++) {
all[i] = new Node(i);
noPre.put(i, all[i]);
}
// For each a depends on b
for (int i = 0; i < p.length; i ++) {
int a = p[i][0], b = p[i][1];
all[b].addDependant(all[a]);// Record a as b's dependant
noPre.remove(a); // a has prerequisites, so need
remove from the hash map
}
int[] result = new int[numCourses];
int index = 0;
// Output and remove each node in "noPre" since they are all
independant
while (!noPre.isEmpty()) {
Object[] allNoPre = noPre.values().toArray(); // toArray to
avoid iterator on a changing hash map (which is undefined behavior)
noPre.clear();
for (int i = 0; i < allNoPre.length; i++) {
Node n = (Node)allNoPre[i];
result[index] = n.id; index ++;
Object[] allPreOf = n.preOf.toArray();
for (int j = 0; j < allPreOf.length; j ++) {
Node dp = (Node)allPreOf[j];
// Each of n's dependants now has one less prerequisite,
and potentially becomes free (no prerequisites)
if ( (-- dp.numOfPre) == 0)
noPre.put(dp.id, dp);
}
}
}
if (index < numCourses) return new int[0];// Some courses not output
yet, but "noPre" is empty, fail
else return result; // All courses in result,
success
}
}
