Share my Java solution with detail comment


  • 4
    J

    This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

    Thus, we need to come up with a DFS algorithm to detect a cycle in the directed graph, here I used HashSet and recursion stack to detect cycle. For example, if we have two vertices connected with each other(1->0, 0->1). if we start DFS with vertex 1, add vertex 1 into HashSet. Then we explore further finding vertex 0 is the neighbor of vertex 1. Then add vertex 0 into HashSet. Keep exploring the neighbor of vertex 0 until we realized that we already have 1 in HashSet. Cycle Detected!

    public class Solution {
    Set<Integer> set=new HashSet<Integer>();
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    	 boolean result=true; //can finish
         boolean[] explored=new boolean[numCourses];//mark all nodes as unexplored
         for(int i=0; i<numCourses; i++){
             if(!explored[i])
                result=findCycle(i, explored, prerequisites, result);//for each unexplored vertex in the graph, call findCycle..
         }
         return result;
    }
    
    public boolean findCycle(int v, boolean[] explored, int[][] prerequisites, boolean flag){// v is the vertex
    	if(flag==false) return flag; //we already found a cycle, no need to search anymore.
        if(set.add(v)){
            }//add vertex into set
        else{
            flag=false;
            return flag;//find a cycle
        } 
        for(int[] list : prerequisites){//for each unexplored vertex s connected to vertex v, call findCycle.
            if(list[1]==v && !explored[list[0]]){
               flag=findCycle(list[0], explored, prerequisites, flag);
            }
        }
        set.remove(v);  //remove the vertex v in hashset set
        explored[v]=true;   //mark this vertex v as explored
        return flag;
      }
    }

  • 0
    Y

    Buggy, can not be right. Two obvious issues:

    1. Ignore cycle in the middle;
    2. the logic determining cycle.

  • 0
    Y

    Read the code carefully and you will see the algorithm considers all possibilities and determining the cycle logic is correct.
    very good and clear solution. The idea is: start from a graph, mark every vertex as unexplored. Then for each unexplored vertex, do DFS. Here DFS is the function findCycle(). In findCycle(), for each edge starting from the vertex, if the edge is unexplored, then do DFS recursively.


Log in to reply
 

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