A golang solution


  • 0
    N
    func dfs(i int, m map[int][]int, book map[int]struct{}) bool {
    	if _, ok := m[i]; !ok {
    		return true
    	}
    	book[i] = struct{}{}
    
    	for _, e := range m[i] {
    		if _, ok := book[e]; ok {
    			return false
    		}
    		book[e] = struct{}{}
    		if dfs(e, m, book) == false {
    			return false
    		}
    		delete(book, e)
    	}
    	return true
    }
    
    func canFinish(numCourses int, prerequisites [][]int) bool {
    	m := make(map[int][]int)
    
    	for _, v := range prerequisites {
    		m[v[0]] = append(m[v[0]], v[1])
    	}
    
    	for i := 0; i < numCourses; i++ {
    		book := make(map[int]struct{})
    		if dfs(i, m, book) == false {
    			return false
    		}
    	}
    
    	return true
    }
    

Log in to reply
 

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