Advanced Graph Algorithms

# python
# LC 1192 - Critical Connections in a Network
# IDEA: Tarjan low-link; tree edge u -> v is a bridge iff low[v] > disc[u]
# time = O(V + E), space = O(V + E)
import sys

def criticalConnections(n, connections):
    sys.setrecursionlimit(max(1000, 2 * n + 10))   # the DFS can be n deep
    graph = [[] for _ in range(n)]
    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)

    disc = [-1] * n          # discovery time, -1 = unvisited
    low = [0] * n            # lowest disc reachable from u's subtree via one back edge
    timer = [0]
    bridges = []

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph[u]:
            if v == parent:
                continue                        # do not walk straight back up the tree edge
            if disc[v] == -1:                   # tree edge
                dfs(v, u)
                low[u] = min(low[u], low[v])    # pull the child's reach up
                if low[v] > disc[u]:            # v's subtree cannot reach u or above
                    bridges.append([u, v])
            else:                               # back edge
                low[u] = min(low[u], disc[v])

    for start in range(n):                      # the loop also covers a disconnected graph
        if disc[start] == -1:
            dfs(start, -1)
    return bridges

// java
// LC 1192 - Critical Connections in a Network
// IDEA: Tarjan low-link; tree edge u -> v is a bridge iff low[v] > disc[u]
// time = O(V + E), space = O(V + E)
class Solution {
    private List<List<Integer>> graph;
    private int[] disc;
    private int[] low;
    private int timer;
    private List<List<Integer>> bridges;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (List<Integer> e : connections) {
            graph.get(e.get(0)).add(e.get(1));
            graph.get(e.get(1)).add(e.get(0));
        }
        disc = new int[n];
        low = new int[n];
        Arrays.fill(disc, -1);
        timer = 0;
        bridges = new ArrayList<>();
        for (int start = 0; start < n; start++) {
            if (disc[start] == -1) {
                dfs(start, -1);
            }
        }
        return bridges;
    }

    private void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        for (int v : graph.get(u)) {
            if (v == parent) {
                continue;
            }
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    bridges.add(Arrays.asList(u, v));
                }
            } else {
                low[u] = Math.min(low[u], disc[v]);   // back edge: disc[v], not low[v]
            }
        }
    }
}

step                  disc  low (after)              note
dfs(0)                0:0   low0=0
  dfs(1) from 0       1:1   low1=1
    dfs(2) from 1     2:2   2 sees 0 (visited)  -> low2 = min(2, disc0=0) = 0
    back in 1                low1 = min(1, low2=0) = 0;  low2=0 > disc1=1? no
    dfs(3) from 1     3:3   3 sees only its parent      low3 = 3
    back in 1                low3=3 > disc1=1  -> bridge [1, 3]
  back in 0                  low0 = 0;  low1=0 > disc0=0? no
result: [[1, 3]]

# python
# Tarjan SCC
# IDEA: v roots an SCC when low[v] == disc[v]; pop the path stack down to v
# time = O(V + E), space = O(V)
def tarjan_scc(n, graph):
    disc = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    sccs = []
    timer = [0]

    def dfs(v):
        disc[v] = low[v] = timer[0]
        timer[0] += 1
        stack.append(v)
        on_stack[v] = True
        for u in graph[v]:
            if disc[u] == -1:
                dfs(u)
                low[v] = min(low[v], low[u])
            elif on_stack[u]:                   # back edge into the open SCC
                low[v] = min(low[v], disc[u])
        if low[v] == disc[v]:                   # v is the root of an SCC
            component = []
            while True:
                u = stack.pop()
                on_stack[u] = False
                component.append(u)
                if u == v:
                    break
            sccs.append(component)

    for v in range(n):
        if disc[v] == -1:
            dfs(v)
    return sccs

# 0 -> 1 -> 2 -> 0, 2 -> 3, 3 -> 4 -> 5 -> 3  =>  [[5, 4, 3], [2, 1, 0]]

# python
# Tarjan articulation points
# IDEA: non-root u is a cut vertex iff some child has low[child] >= disc[u]; root iff >= 2 children
# time = O(V + E), space = O(V + E)
def articulation_points(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    disc = [-1] * n
    low = [0] * n
    cut = set()
    timer = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in graph[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= disc[u]:
                    cut.add(u)
            else:
                low[u] = min(low[u], disc[v])
        if parent == -1 and children >= 2:
            cut.add(u)

    for start in range(n):
        if disc[start] == -1:
            dfs(start, -1)
    return sorted(cut)

# edges [[0,1],[1,2],[2,0],[1,3],[3,4]]  =>  [1, 3]

# python
# LC 332 - Reconstruct Itinerary
# IDEA: Hierholzer; walk consuming edges, append a node when it is stuck, reverse at the end
# time = O(E log E), space = O(E)
from collections import defaultdict

def findItinerary(tickets):
    graph = defaultdict(list)
    # sort descending so list.pop() from the tail yields the smallest airport first
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)

    route = []
    stack = ["JFK"]
    while stack:
        airport = stack[-1]
        if graph[airport]:
            stack.append(graph[airport].pop())   # consume one ticket, walk forward
        else:
            route.append(stack.pop())            # stuck: this airport is final, post-order
    return route[::-1]

// java
// LC 332 - Reconstruct Itinerary
// IDEA: Hierholzer; walk consuming edges, append a node when it is stuck, reverse at the end
// time = O(E log E), space = O(E)
public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
    }
    LinkedList<String> route = new LinkedList<>();
    Deque<String> stack = new ArrayDeque<>();
    stack.push("JFK");
    while (!stack.isEmpty()) {
        PriorityQueue<String> next = graph.get(stack.peek());
        if (next != null && !next.isEmpty()) {
            stack.push(next.poll());          // consume the smallest ticket
        } else {
            route.addFirst(stack.pop());      // post-order, reversed as it is built
        }
    }
    return route;
}

stack                        action
[JFK]                        take ATL (smallest)
[JFK ATL]                    take JFK
[JFK ATL JFK]                take SFO
[JFK ATL JFK SFO]            take ATL
[JFK ATL JFK SFO ATL]        take SFO
[JFK ATL JFK SFO ATL SFO]    SFO stuck -> route [SFO]; then ATL, SFO, JFK, ATL, JFK pop in turn
route reversed: JFK ATL JFK SFO ATL SFO

# python
# LC 753 - Cracking the Safe
# IDEA: Hierholzer on the de Bruijn graph; node = last n-1 digits, edge = one appended digit
# time = O(n * k^n), space = O(n * k^n)
def crackSafe(n, k):
    start = "0" * (n - 1)
    next_digit = {}               # node -> the next digit (edge) it has not used yet
    stack = [(start, "")]         # (node, digit of the edge that led here)
    digits = []
    while stack:
        node, came_by = stack[-1]
        d = next_digit.get(node, 0)
        if d < k:
            next_digit[node] = d + 1                   # consume edge `d` out of `node`
            stack.append(((node + str(d))[1:], str(d)))
        else:
            stack.pop()                                # stuck: emit in post-order
            digits.append(came_by)
    return start + "".join(reversed(digits))

# python
# LC 886 - Possible Bipartition
# IDEA: parity DSU; union a with twin(b) and b with twin(a); a and b already joined -> odd cycle
# time = O((n + m) * α(n)), space = O(n)
def possibleBipartition(n, dislikes):
    parent = list(range(2 * (n + 1)))      # people 1..n, twins n+1..2n+1

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x

    def union(x, y):
        parent[find(x)] = find(y)

    for a, b in dislikes:
        if find(a) == find(b):             # forced into the same group already
            return False
        union(a, b + n + 1)                # a joins b's opposite
        union(b, a + n + 1)                # b joins a's opposite
    return True

// java
// LC 886 - Possible Bipartition
// IDEA: parity DSU; union a with twin(b) and b with twin(a); a and b already joined -> odd cycle
// time = O((n + m) * α(n)), space = O(n)
class Solution {
    private int[] parent;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        parent = new int[2 * (n + 1)];                    // people 1..n, twins n+1..2n+1
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        for (int[] d : dislikes) {
            int a = d[0], b = d[1];
            if (find(a) == find(b)) return false;         // forced into the same group already
            union(a, b + n + 1);                          // a joins b's opposite
            union(b, a + n + 1);                          // b joins a's opposite
        }
        return true;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];                // path halving
            x = parent[x];
        }
        return x;
    }

    private void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

# python
# LC 1820 - Maximum Number of Accepted Invitations
# IDEA: Kuhn; for each boy, DFS for an augmenting path (free girl, or re-seat her partner)
# time = O(m * m * n), space = O(n)
def maximumInvitations(grid):
    m, n = len(grid), len(grid[0])
    partner = [-1] * n                     # partner[girl] = boy, or -1

    def try_match(boy, tried):
        for girl in range(n):
            if grid[boy][girl] and not tried[girl]:
                tried[girl] = True         # each girl is tried once per augmenting search
                if partner[girl] == -1 or try_match(partner[girl], tried):
                    partner[girl] = boy
                    return True
        return False

    matched = 0
    for boy in range(m):
        if try_match(boy, [False] * n):
            matched += 1
    return matched

// java
// LC 1820 - Maximum Number of Accepted Invitations
// IDEA: Kuhn; for each boy, DFS for an augmenting path (free girl, or re-seat her partner)
// time = O(m * m * n), space = O(n)
public int maximumInvitations(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] partner = new int[n];
    Arrays.fill(partner, -1);
    int matched = 0;
    for (int boy = 0; boy < m; boy++) {
        if (tryMatch(grid, boy, new boolean[n], partner)) {
            matched++;
        }
    }
    return matched;
}

private boolean tryMatch(int[][] grid, int boy, boolean[] tried, int[] partner) {
    for (int girl = 0; girl < grid[0].length; girl++) {
        if (grid[boy][girl] == 1 && !tried[girl]) {
            tried[girl] = true;
            if (partner[girl] == -1 || tryMatch(grid, partner[girl], tried, partner)) {
                partner[girl] = boy;
                return true;
            }
        }
    }
    return false;
}

# python
# Edmonds-Karp max flow on a capacity matrix
# IDEA: BFS the residual graph for a shortest augmenting path; push its bottleneck; repeat
# time = O(V * E^2), space = O(V^2)
from collections import deque

def max_flow(capacity, source, sink):
    n = len(capacity)
    residual = [row[:] for row in capacity]
    flow = 0
    while True:
        parent = [-1] * n
        parent[source] = source
        queue = deque([source])
        while queue and parent[sink] == -1:
            u = queue.popleft()
            for v in range(n):
                if parent[v] == -1 and residual[u][v] > 0:
                    parent[v] = u
                    queue.append(v)
        if parent[sink] == -1:                 # no augmenting path left
            return flow
        bottleneck = float('inf')
        v = sink
        while v != source:
            bottleneck = min(bottleneck, residual[parent[v]][v])
            v = parent[v]
        v = sink
        while v != source:
            residual[parent[v]][v] -= bottleneck
            residual[v][parent[v]] += bottleneck   # lets a later path cancel this push
            v = parent[v]
        flow += bottleneck

# python
# LC 1042 - Flower Planting With No Adjacent
# IDEA: degree <= 3 and 4 colours, so a free colour always exists; take the first one
# time = O(V + E), space = O(V + E)
def gardenNoAdj(n, paths):
    graph = [[] for _ in range(n + 1)]
    for a, b in paths:
        graph[a].append(b)
        graph[b].append(a)

    colour = [0] * (n + 1)                 # 0 = not coloured yet; gardens are 1..n
    for garden in range(1, n + 1):
        used = set()
        for neighbour in graph[garden]:
            used.add(colour[neighbour])
        for c in (1, 2, 3, 4):
            if c not in used:
                colour[garden] = c
                break
    return colour[1:]

// java
// LC 1042 - Flower Planting With No Adjacent
// IDEA: degree <= 3 and 4 colours, so a free colour always exists; take the first one
// time = O(V + E), space = O(V + E)
public int[] gardenNoAdj(int n, int[][] paths) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] p : paths) {
        graph.get(p[0]).add(p[1]);
        graph.get(p[1]).add(p[0]);
    }
    int[] colour = new int[n];               // colour[g - 1]; 0 = not coloured yet
    for (int garden = 1; garden <= n; garden++) {
        boolean[] used = new boolean[5];
        for (int neighbour : graph.get(garden)) {
            used[colour[neighbour - 1]] = true;
        }
        for (int c = 1; c <= 4; c++) {
            if (!used[c]) {
                colour[garden - 1] = c;
                break;
            }
        }
    }
    return colour;
}