Graph Algorithms

# For edges list
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # Undirected

# For weighted edges
graph = defaultdict(list)
for u, v, w in edges:
    graph[u].append((v, w))

# For unweighted
graph = [[0] * n for _ in range(n)]
for u, v in edges:
    graph[u][v] = 1
    graph[v][u] = 1  # Undirected

# For weighted
graph = [[float('inf')] * n for _ in range(n)]
for u, v, w in edges:
    graph[u][v] = w

# 4-directional movement
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

# 8-directional movement
directions = [(0, 1), (1, 0), (0, -1), (-1, 0),
              (1, 1), (1, -1), (-1, 1), (-1, -1)]

# Check bounds
def is_valid(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

# undirected: add BOTH directions -- forgetting this is the most common graph bug
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

# directed: one direction only, and degree splits into two counts
out_deg = [0] * n
in_deg = [0] * n
for u, v in edges:
    graph[u].append(v)
    out_deg[u] += 1
    in_deg[v] += 1

# Set for simple visited
visited = set()

# Array for state tracking
# 0: unvisited, 1: visiting, 2: visited
state = [0] * n

# Dictionary for path reconstruction
parent = {}

# python
# LC 547 - Number of Provinces
# IDEA: launch a BFS from every node not yet visited; each launch covers exactly one component
# time = O(n^2), space = O(n)   n^2 because the input is an adjacency matrix
from collections import deque

def findCircleNum(isConnected):
    n = len(isConnected)
    visited = [False] * n
    components = 0
    for start in range(n):
        if visited[start]:
            continue
        components += 1                     # a new launch = a new component
        visited[start] = True
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in range(n):            # one matrix row = node's neighbours
                if isConnected[node][nxt] == 1 and not visited[nxt]:
                    visited[nxt] = True     # mark when enqueued
                    queue.append(nxt)
    return components

// java
// LC 547 - Number of Provinces
// IDEA: launch a BFS from every node not yet visited; each launch covers exactly one component
// time = O(n^2), space = O(n)
public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int components = 0;
    for (int start = 0; start < n; start++) {
        if (visited[start]) {
            continue;
        }
        components++;                        // a new launch = a new component
        visited[start] = true;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int nxt = 0; nxt < n; nxt++) {
                if (isConnected[node][nxt] == 1 && !visited[nxt]) {
                    visited[nxt] = true;     // mark when enqueued
                    queue.offer(nxt);
                }
            }
        }
    }
    return components;
}

# python
# LC 841 - Keys and Rooms
# IDEA: DFS from room 0 with an explicit stack; visited = every room reached so far
# time = O(V + E), space = O(V)
def canVisitAllRooms(rooms):
    visited = {0}
    stack = [0]
    while stack:
        room = stack.pop()
        for key in rooms[room]:
            if key not in visited:
                visited.add(key)            # mark when pushed: each room is pushed once
                stack.append(key)
    return len(visited) == len(rooms)

// java
// LC 841 - Keys and Rooms
// IDEA: DFS from room 0 with an explicit stack; visited = every room reached so far
// time = O(V + E), space = O(V)
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    boolean[] visited = new boolean[rooms.size()];
    visited[0] = true;
    int reached = 1;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    while (!stack.isEmpty()) {
        int room = stack.pop();
        for (int key : rooms.get(room)) {
            if (!visited[key]) {
                visited[key] = true;         // mark when pushed: each room is pushed once
                reached++;
                stack.push(key);
            }
        }
    }
    return reached == rooms.size();
}

# python
# LC 797 - All Paths From Source to Target
# IDEA: DFS + backtracking on a DAG (no visited set needed)
# time = O(2^n * n), space = O(n) excluding output
class Solution(object):
    def allPathsSourceTarget(self, graph):
        n = len(graph)
        res, path = [], [0]

        def dfs(u):
            if u == n - 1:
                res.append(path[:])    # copy!
                return
            for v in graph[u]:
                path.append(v)
                dfs(v)
                path.pop()             # backtrack

        dfs(0)
        return res

# [[1,2],[3],[3],[]] -> [[0,1,3],[0,2,3]]

// java
// LC 797 - All Paths From Source to Target
// IDEA: DFS + backtracking on a DAG. No visited set (DAG => no cycles),
//       and a node may legitimately appear in many different paths.
// time = O(2^n * n), space = O(n) excluding output
import java.util.*;

public class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);                       // start node is always in the path
        dfs(graph, 0, path, res);
        return res;
    }

    private void dfs(int[][] graph, int u, List<Integer> path, List<List<Integer>> res) {
        if (u == graph.length - 1) {
            res.add(new ArrayList<>(path));   // copy, not the live list
            return;
        }
        for (int v : graph[u]) {
            path.add(v);
            dfs(graph, v, path, res);
            path.remove(path.size() - 1);     // backtrack
        }
    }
}

# python
# LC 684 - Redundant Connection
# IDEA: union every edge; the first edge whose two ends already share a root closes the cycle
# time = O(E * α(n)), space = O(n)
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n                       # number of components

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:        # path compression: point each node at the root
            next_node = self.parent[x]
            self.parent[x] = root
            x = next_node
        return root

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False                     # already connected: this edge is a cycle
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x  # hang the shorter tree under the taller
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        self.count -= 1
        return True

def findRedundantConnection(edges):
    uf = UnionFind(len(edges) + 1)           # nodes are 1..n and n == len(edges)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []

// java
// LC 684 - Redundant Connection
// IDEA: union every edge; the first edge whose two ends already share a root closes the cycle
// time = O(E * α(n)), space = O(n)
class UnionFind {
    private final int[] parent;
    private final int[] rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        while (parent[x] != root) {          // path compression
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;                    // already connected: this edge is a cycle
        }
        if (rank[rootX] < rank[rootY]) {
            int tmp = rootX;
            rootX = rootY;
            rootY = tmp;
        }
        parent[rootY] = rootX;
        if (rank[rootX] == rank[rootY]) {
            rank[rootX]++;
        }
        return true;
    }
}

public int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return edge;
        }
    }
    return new int[0];
}

# python
# LC 207 - Course Schedule
# IDEA: keep taking a course with no unmet prerequisite; a cycle leaves courses never taken
# time = O(V + E), space = O(V + E)
from collections import deque

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, pre in prerequisites:        # [a, b] means b must come before a
        graph[pre].append(course)
        indegree[course] += 1
    queue = deque()
    for course in range(numCourses):
        if indegree[course] == 0:            # every source, not only node 0
            queue.append(course)
    taken = 0
    while queue:
        node = queue.popleft()
        taken += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return taken == numCourses

// java
// LC 207 - Course Schedule
// IDEA: keep taking a course with no unmet prerequisite; a cycle leaves courses never taken
// time = O(V + E), space = O(V + E)
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    int[] indegree = new int[numCourses];
    for (int[] p : prerequisites) {          // [a, b] means b must come before a
        graph.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }
    int taken = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        taken++;
        for (int nxt : graph.get(node)) {
            indegree[nxt]--;
            if (indegree[nxt] == 0) {
                queue.offer(nxt);
            }
        }
    }
    return taken == numCourses;
}

numCourses = 2, prerequisites = [[1,0]]        edge 0 -> 1
indegree = [0, 1]   queue = [0]
pop 0  taken=1  indegree[1] -> 0, push 1
pop 1  taken=2                                  2 == 2 -> True

prerequisites = [[1,0],[0,1]]                  edges 0 -> 1, 1 -> 0
indegree = [1, 1]   queue = []                  taken=0 -> False (the cycle never empties)

# python
# LC 207 - Course Schedule (three-state DFS)
# IDEA: a cycle exists iff the DFS meets a node that is still on the current path (state 1)
# time = O(V + E), space = O(V + E)
from collections import defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for course, pre in prerequisites:
        graph[course].append(pre)          # course -> what it needs
    state = [0] * numCourses               # 0 = unseen, 1 = on the current path, 2 = done
    def dfs(node):
        if state[node] == 1:
            return False                   # back edge: a cycle
        if state[node] == 2:
            return True
        state[node] = 1
        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        state[node] = 2
        return True
    return all(dfs(c) for c in range(numCourses))

# python
# LC 802 - Find Eventual Safe States
# IDEA: 3-state DFS; a node is unsafe iff its DFS meets a node still on the current path
# time = O(V + E), space = O(V)
def eventualSafeNodes(graph):
    UNVISITED, ON_PATH, SAFE = 0, 1, 2
    state = [UNVISITED] * len(graph)

    def leads_to_cycle(node):
        if state[node] == ON_PATH:          # back edge: node is on the path we came down
            return True
        if state[node] == SAFE:             # finished earlier and proven cycle-free
            return False
        state[node] = ON_PATH
        for nxt in graph[node]:
            if leads_to_cycle(nxt):
                return True                 # leave node ON_PATH: it is unsafe for good
        state[node] = SAFE
        return False

    safe = []
    for node in range(len(graph)):
        if not leads_to_cycle(node):
            safe.append(node)
    return safe

// java
// LC 802 - Find Eventual Safe States
// IDEA: 3-state DFS; a node is unsafe iff its DFS meets a node still on the current path
// time = O(V + E), space = O(V)
private static final int UNVISITED = 0, ON_PATH = 1, SAFE = 2;

public List<Integer> eventualSafeNodes(int[][] graph) {
    int[] state = new int[graph.length];
    List<Integer> safe = new ArrayList<>();
    for (int node = 0; node < graph.length; node++) {
        if (!leadsToCycle(graph, node, state)) {
            safe.add(node);
        }
    }
    return safe;
}

private boolean leadsToCycle(int[][] graph, int node, int[] state) {
    if (state[node] == ON_PATH) {
        return true;                         // back edge
    }
    if (state[node] == SAFE) {
        return false;
    }
    state[node] = ON_PATH;
    for (int nxt : graph[node]) {
        if (leadsToCycle(graph, nxt, state)) {
            return true;                     // node stays ON_PATH: unsafe for good
        }
    }
    state[node] = SAFE;
    return false;
}

# python
# LC 802 - Find Eventual Safe States (Kahn on the reversed graph)
# IDEA: terminals are safe; a node is safe once every out-edge leads to a safe node -> peel backwards
# time = O(V + E), space = O(V + E)
from collections import deque

def eventualSafeNodes(graph):
    n = len(graph)
    reverse = [[] for _ in range(n)]
    out_degree = [0] * n
    for node in range(n):
        out_degree[node] = len(graph[node])
        for nxt in graph[node]:
            reverse[nxt].append(node)      # edge flipped: nxt -> node
    queue = deque(node for node in range(n) if out_degree[node] == 0)  # terminals are safe
    safe = [False] * n
    while queue:
        node = queue.popleft()
        safe[node] = True
        for prev in reverse[node]:
            out_degree[prev] -= 1          # one more of prev's edges leads somewhere safe
            if out_degree[prev] == 0:
                queue.append(prev)
    return [node for node in range(n) if safe[node]]

# python
# LC 785 - Is Graph Bipartite?
# IDEA: BFS paints each neighbour the opposite colour; a same-colour edge means an odd cycle
# time = O(V + E), space = O(V)
from collections import deque

def isBipartite(graph):
    n = len(graph)
    colors = [-1] * n                    # -1 = uncoloured, which also means unvisited
    for start in range(n):               # one BFS per component
        if colors[start] != -1:
            continue
        colors[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == -1:
                    colors[neighbor] = 1 - colors[node]
                    queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False         # same colour on both ends of an edge
    return True

// java
// LC 785 - Is Graph Bipartite?
// IDEA: BFS paints each neighbour the opposite colour; a same-colour edge means an odd cycle
// time = O(V + E), space = O(V)
public boolean isBipartite(int[][] graph) {
    int n = graph.length;
    int[] colors = new int[n];
    Arrays.fill(colors, -1);                 // -1 = uncoloured, which also means unvisited
    for (int start = 0; start < n; start++) {
        if (colors[start] != -1) {
            continue;
        }
        colors[start] = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph[node]) {
                if (colors[neighbor] == -1) {
                    colors[neighbor] = 1 - colors[node];
                    queue.offer(neighbor);
                } else if (colors[neighbor] == colors[node]) {
                    return false;
                }
            }
        }
    }
    return true;
}

# python
# LC 785 - Is Graph Bipartite? (recursive form, same invariant)
# IDEA: colour a node, recurse into neighbours with the opposite colour
# time = O(V + E), space = O(V)
def is_bipartite_dfs(graph):
    n = len(graph)
    colors = [-1] * n

    def dfs(node, color):
        colors[node] = color
        for neighbor in graph[node]:
            if colors[neighbor] == -1:
                if not dfs(neighbor, 1 - color):
                    return False
            elif colors[neighbor] == colors[node]:
                return False
        return True

    for i in range(n):
        if colors[i] == -1 and not dfs(i, 0):
            return False
    return True

Graph Algorithm Selection Flowchart:

1. What is the problem asking for?
   ├── Find shortest path → Continue to 2
   ├── Check connectivity → Use Union-Find or DFS/BFS
   ├── Order with dependencies → Use Topological Sort
   ├── Detect cycles → Use DFS with states or Union-Find
   └── Traverse all nodes → Use BFS or DFS

2. For shortest path problems:
   ├── Unweighted graph → Use BFS
   ├── Non-negative weights → Use Dijkstra
   ├── Negative weights → Use Bellman-Ford
   └── All pairs → Use Floyd-Warshall

3. For connectivity problems:
   ├── Static graph → Use DFS/BFS once
   ├── Dynamic connections → Use Union-Find
   └── Count components → Use either approach

4. For traversal problems:
   ├── Level-by-level → Use BFS
   ├── Path finding → Use DFS with backtracking
   └── State space search → Use BFS for optimal

5. Is the graph special?
   ├── Tree → Simpler DFS/BFS
   ├── DAG → Topological sort possible
   ├── Bipartite → Two-coloring
   └── Grid → Treat as implicit graph