Algoschool

Explore

Level 1

Graphs problems

⁠

https://leetcode.com/problems/keys-and-rooms⁠

⁠

class Solution:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:

visited = set()

def dfs(r):

visited.add(r)

for n in rooms[r]:

if n not in visited:

dfs(n)

dfs(0)

return len(visited) == len(rooms)

⁠

https://leetcode.com/problems/course-schedule/⁠

⁠

class Solution:

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

V = {}

for f, t in prerequisites:

V.setdefault(f, []).append(t)

color = {}

for v in range(0, numCourses):

color[v] = 0

def dfs(v):

color[v] = 1

for n in V.get(v, []):

if color[n] == 0:

if not dfs(n):

return False

elif color[n] == 1:

return False

color[v] = 2

return True

for v in range(0, numCourses):

if not dfs(v):

return False

return True

⁠

https://leetcode.com/problems/shortest-path-to-get-food⁠

⁠

from collections import deque

class Solution:

def getFood(self, grid: List[List[str]]) -> int:

start = None

for i in range(len(grid)):

for j in range(len(grid[i])):

if grid[i][j] == '*':

start = (i, j)

break

q = deque()

q.append((start, 0))

visited = set()

print('start', start)

visited.add(start)

i = 0

while q:

i += 1

(c, d) = q.pop()

if grid[c[0]][c[1]] == '#':

return d

for (ix, jx) in [(-1, 0), (0, -1), (0, 1), (1, 0)]:

n = (c[0] + ix, c[1] + jx)

if n[0] < 0 or n[1] < 0 or n[0] >= len(grid) or n[1] >= len(grid[0]):

continue

if grid[n[0]][n[1]] == 'X':

continue

if n not in visited:

visited.add(n)

q.appendleft((n, d + 1))

return -1

⁠

https://leetcode.com/problems/rotting-oranges/⁠

⁠

from collections import deque

DIRS = [(0, 1), (1, 0), (-1,0), (0, -1)]

class Solution:

def orangesRotting(self, grid: List[List[int]]) -> int:

d = deque()

visited = set()

count = 0

for i in range(len(grid)):

for j in range(len(grid[i])):

if grid[i][j] == 2:

visited.add((i, j))

d.append(((i, j), 0))

if grid[i][j] in (1, 2):

count += 1

maxc = None

while d:

(i, j), c = d.pop()

if maxc is None or c > maxc:

maxc = c

for (ix, jx) in DIRS:

ni, nj = i + ix, j + jx

if ni < 0 or nj < 0 or ni >= len(grid) or nj >= len(grid[ni]):

continue

if (ni, nj) in visited or grid[ni][nj] == 0:

continue

visited.add((ni, nj))

d.appendleft(((ni, nj), c + 1))

if len(visited) != count:

return -1

return maxc if maxc else 0

⁠

https://leetcode.com/problems/max-area-of-island⁠

⁠

class Solution:

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def dfs(i, j):

res = 1

grid[i][j] = 0

for (ix, jx) in DIRS:

ni, nj = i + ix, j + jx

if ni < 0 or nj < 0 or ni >= len(grid) or nj >= len(grid[ni]):

continue

if grid[ni][nj] == 0:

continue

res += dfs(ni, nj)

return res

maxc = 0

for i in range(len(grid)):

for j in range(len(grid[i])):

if grid[i][j] == 1:

c = dfs(i, j)

maxc = max(c, maxc)

return maxc

⁠

https://leetcode.com/problems/course-schedule-ii⁠

⁠

class Solution:

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

G = [[] for v in range(numCourses)]

for (a, b) in prerequisites:

G[b].append(a)

res = []

colors = [0 for v in range(numCourses)]

def top_sort(v):

colors[v] = 1

for n in G[v]:

if colors[n] == 1:

return False

elif colors[n] == 0:

if not top_sort(n):

return False

res.append(v)

colors[v] = 2

return True

for v in range(numCourses):

if colors[v] == 0:

if not top_sort(v):

return []

res.reverse()

return res

⁠

https://leetcode.com/problems/walls-and-gates/submissions/⁠

⁠

from collections import deque

DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

class Solution:

def wallsAndGates(self, rooms: List[List[int]]) -> None:

def bfs(i, j):

q = deque()

q.append((i, j))

n = 0

visited = set()

visited.add((i, j))

while q:

for _ in range(len(q)):

(i, j) = q.popleft()

rooms[i][j] = min(n, rooms[i][j])

visited.add((i, j))

for (ix, jx) in DIRS:

ni, nj = i + ix, j + jx

if ni < 0 or nj < 0 or ni >= len(rooms) or nj >= len(rooms[ni]):

continue

if rooms[ni][nj] == -1:

continue

if rooms[ni][nj] == 0:

continue

if (ni, nj) in visited:

continue

q.append((ni, nj))

n += 1

for i in range(len(rooms)):

for j in range(len(rooms[i])):

if rooms[i][j] == 0:

bfs(i, j)

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.