Graphs: BFS, cycles and topological sort

from collections import defaultdict, deque

edges = [("extract_orders", "clean_orders"),
         ("extract_customers", "dim_customer"),
         ("clean_orders", "fact_orders"),
         ("dim_customer", "fact_orders"),
         ("fact_orders", "daily_report"),
         ("dim_customer", "daily_report")]

def topo_order(edges):                       # Kahn's algorithm
    graph, indegree = defaultdict(list), defaultdict(int)
    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1
        indegree.setdefault(a, 0)
    ready = deque(sorted(n for n, d in indegree.items() if d == 0))
    order = []
    while ready:
        n = ready.popleft()
        order.append(n)
        for nxt in graph[n]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:           # all its inputs are done
                ready.append(nxt)
    if len(order) < len(indegree):
        raise ValueError("cycle: some tasks wait on each other")
    return order

print(topo_order(edges))
try:
    topo_order(edges + [("daily_report", "extract_orders")])
except ValueError as e:
    print(e)

['extract_customers', 'extract_orders', 'dim_customer', 'clean_orders', 'fact_orders', 'daily_report']
cycle: some tasks wait on each other

from collections import deque

grid = ["11000",
        "11010",
        "00011",
        "00000"]

def islands(grid):
    rows, cols, seen, count = len(grid), len(grid[0]), set(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1                       # new island: flood it
                q = deque([(r, c)]); seen.add((r, c))
                while q:
                    y, x = q.popleft()
                    for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        ny, nx = y + dy, x + dx
                        inside = 0 <= ny < rows and 0 <= nx < cols
                        if (inside and grid[ny][nx] == "1"
                                and (ny, nx) not in seen):
                            seen.add((ny, nx)); q.append((ny, nx))
    return count

print(islands(grid))

2