Python 10 line solution, very simple


  • -1
    R
    def canFinish(self, numCourses, prerequisites):
        forbid = {}  # maintaining a predecessor table
        for x,y in prerequisites:                
            if y in forbid:
                forbid[y].append(x)
            else:
                forbid[y] = [x]  
            if x in forbid:
                forbid[y].extend([s for s in forbid[x] if s not in forbid[y]])  # only need to add the predecessor's predecessor
                if y in forbid[x]:  return False # conflict                    
        return True

  • 0
    L

    sorry,I donot think itis a good answer. In the case 3, [[1,0],[2,1],[0,2]], the result is wrong.


  • 0
    R

    yes you are right. This is incorrect. The testing cases are problematic


Log in to reply
 

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