Graph problems

490. The Maze

Initially, I made a mistake by putting the seen = {(i,j)} within the while open_list. It should be put before the while open_list. If not, we will have an infinite loop.

The DFS complexity is O(V+E) since we don’t have that many E, the complexity is O(V) as O(V+E)<O(V+V) =O(2V). V is approximately n*n and for each DFS for each direction, if we want to reach the wall or boundary, we have to check at most n cells. It have the complexity of O(n). So the overall complexity will be O(n³). Since n is only 100, n³ is doable.

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        if not maze or not maze[0]:return False
        R, C = len(maze), len(maze[0])
        def dfs(i,j):
            open_list = [(i,j)]
            seen = {(i,j)}
            while open_list:
                i,j = open_list.pop()
                next_steps = []
                for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]:
                    r, c = i, j
                    while True:
                        r += di
                        c += dj
                        if r<0 or r>=R or c<0 or c>=C or maze[r][c]:
                            r -= di
                            c -= dj
                            break
                        
                    if (r,c) not in seen:
                        seen.add((r,c))
                        if [r,c] == destination:return True
                        
                        open_list.append((r,c))
            return False
        return dfs(*start)

323. Number of Connected Components in an Undirected Graph

DFS(96ms)

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        visited = [False]*n
        def dfs(i):
            visited[i]=True
            for j in graph[i]:
                if not visited[j]:
                    dfs(j)
        graph = collections.defaultdict(list)
        for a,b in edges:
            graph[a].append(b)
            graph[b].append(a)
        res = 0
        for i in range(n):
            if not visited[i]:
                res+=1
                dfs(i)
        return res

union find (124 ms)

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = {}
        def find(x):
            uf.setdefault(x, x)
            if uf[x]!=x:
                uf[x] = find(uf[x])
            return uf[x]
        def union(x,y):
            uf[find(y)] = find(x)
        
        for a,b in edges:
            union(a,b)
        return len({find(i) for i in range(n)})