My Java BFS solution

• ``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
int[] indegree = new int[numCourses];
int count = numCourses;
for (int i = 0; i < numCourses; i++) {
map.put(i, new ArrayList<Integer>());
}
for (int i = 0; i < prerequisites.length; i++) {
indegree[prerequisites[i][1]]++;
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int current = queue.poll();
for (int i : map.get(current)) {
if (--indegree[i] == 0) {
queue.offer(i);
}
}
count--;
}
return count == 0;
}
}``````

• just use topo theory. a simple solution.

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(numCourses<=1) return true;
HashMap<Integer,HashSet<Integer>> map=new HashMap<Integer,HashSet<Integer>>();
for(int i=0;i<prerequisites.length;++i){
if(!map.containsKey(prerequisites[i][0])){
map.put(prerequisites[i][0],new HashSet<Integer>());
}
}
HashSet<Integer> finished=new HashSet<Integer>();
for(int i=0;i<numCourses;++i)
if(!map.containsKey(i))
while(map.size()>0){
if(!find(map,finished))
return false;
}
return true;
}
boolean find(HashMap<Integer,HashSet<Integer>> map,HashSet<Integer> finished){
for(Integer key: map.keySet()){
HashSet<Integer> values=map.get(key);
if(finished.containsAll(values)){
map.remove(key);
return true;
}
}
return false;
}
}``````

• How about if the input is multiple connected components, your solution seems cannot handle this situation.

• Brilliant code

• What does multiple connected components mean?@kangwang

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.