Day 39 of LeetCode

Documenting LeetCode solving.

Q110

207. Course Schedule

Medium. Graph

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # {crs : [pres]}
        preMap = {i : [] for i in range(numCourses)}
        for crs, pre in prerequisites:
            preMap[crs].append(pre)
        # all courses along the current DFS path
        visit = set()

        def dfs(crs):
            # detect the loop
            if crs in visit:
                return False
            if preMap[crs] == []:
                return True

            visit.add(crs)
            for pre in preMap[crs]:
                if not dfs(pre):
                    return False
            # remove the course after visiting
            visit.remove(crs)
            # set it to [] as all pre can be completed
            preMap[crs] = []

            return True

        # using a loop as the graph might not be fully connected
        for i in range(numCourses):
            if not dfs(i):
                return False

        return True

Q111

Graph Valid Tree.

Medium. Graph

class Solution:
    """
    @param n: An integer
    @param edges: a list of undirected edges
    @return: true if it's a valid tree, or false
    """
    def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
        # a valid tree: no loop and all nodes are connected

        # adjacency list
        adj = {i:[] for i in range(n)}
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)

        visit = set()
        def dfs(i, prev):
            if i in visit:
                return False

            visit.add(i)
            for j in adj[i]:
                # if j is the node we came from
                if j == prev:
                    continue
                if not dfs(j, i):
                    return False

            return True
        # n == len(visit): make sure all nodes are connected
        return dfs(0, -1) and n == len(visit)