進階圖論演算法

# Tarjan's Algorithm for SCC
def tarjan_scc(n, graph):
    """
    Find all strongly connected components using Tarjan's algorithm.

    Args:
        n: number of vertices (0 to n-1)
        graph: adjacency list (directed graph)

    Returns:
        List of SCCs, where each SCC is a list of vertices

    Time: O(V + E)
    Space: O(V)
    """
    disc = [-1] * n  # Discovery times
    low = [-1] * n   # Lowest reachable
    on_stack = [False] * n
    stack = []
    sccs = []
    timer = [0]  # Use list for mutability

    def dfs(v):
        # Initialize discovery time and low value
        disc[v] = low[v] = timer[0]
        timer[0] += 1
        stack.append(v)
        on_stack[v] = True

        # Explore neighbors
        for u in graph[v]:
            if disc[u] == -1:
                # Unvisited neighbor
                dfs(u)
                low[v] = min(low[v], low[u])
            elif on_stack[u]:
                # Back edge to vertex on stack
                low[v] = min(low[v], disc[u])

        # If v is a root of SCC, pop the SCC
        if low[v] == disc[v]:
            scc = []
            while True:
                u = stack.pop()
                on_stack[u] = False
                scc.append(u)
                if u == v:
                    break
            sccs.append(scc)

    # Run DFS from each unvisited vertex
    for i in range(n):
        if disc[i] == -1:
            dfs(i)

    return sccs

# Example:
# graph = {0: [1], 1: [2], 2: [0, 3], 3: [4], 4: [5], 5: [3]}
#    0 → 1 → 2
#    ↑       ↓
#    └───────┘    3 ⇄ 4 → 5
#                     ↑   ↓
#                     └───┘
# SCCs: [[0, 2, 1], [3, 5, 4]]

// Tarjan's SCC Algorithm
/**
 * LC 1192 - Critical Connections in a Network (related)
 *
 * time = O(V + E)
 * space = O(V)
 */
class TarjanSCC {
    private int timer = 0;
    private int[] disc;
    private int[] low;
    private boolean[] onStack;
    private Stack<Integer> stack;
    private List<List<Integer>> sccs;

    public List<List<Integer>> findSCCs(int n, List<List<Integer>> graph) {
        disc = new int[n];
        low = new int[n];
        onStack = new boolean[n];
        stack = new Stack<>();
        sccs = new ArrayList<>();

        Arrays.fill(disc, -1);
        Arrays.fill(low, -1);

        // DFS from each unvisited vertex
        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) {
                dfs(i, graph);
            }
        }

        return sccs;
    }

    private void dfs(int v, List<List<Integer>> graph) {
        // Initialize
        disc[v] = low[v] = timer++;
        stack.push(v);
        onStack[v] = true;

        // Explore neighbors
        for (int u : graph.get(v)) {
            if (disc[u] == -1) {
                // Unvisited
                dfs(u, graph);
                low[v] = Math.min(low[v], low[u]);
            } else if (onStack[u]) {
                // Back edge
                low[v] = Math.min(low[v], disc[u]);
            }
        }

        // Root of SCC found
        if (low[v] == disc[v]) {
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int u = stack.pop();
                onStack[u] = false;
                scc.add(u);
                if (u == v) break;
            }
            sccs.add(scc);
        }
    }
}

# Tarjan's Algorithm for Bridges
def find_bridges(n, edges):
    """
    Find all bridges (critical connections) in an undirected graph.

    Args:
        n: number of vertices
        edges: list of [u, v] edges

    Returns:
        List of bridges (critical edges)

    Time: O(V + E)
    Space: O(V + E)
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    disc = [-1] * n
    low = [-1] * n
    bridges = []
    timer = [0]

    def dfs(v, parent):
        disc[v] = low[v] = timer[0]
        timer[0] += 1

        for u in graph[v]:
            if u == parent:
                # Skip edge to parent (undirected graph)
                continue

            if disc[u] == -1:
                # Unvisited neighbor
                dfs(u, v)
                low[v] = min(low[v], low[u])

                # Check if (v, u) is a bridge
                if low[u] > disc[v]:
                    bridges.append([v, u])
            else:
                # Back edge
                low[v] = min(low[v], disc[u])

    # Run DFS from each component
    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return bridges

# Example:
# n = 4, edges = [[0,1],[1,2],[2,0],[1,3]]
#
#    0 --- 1 --- 3
#     \   /
#      \ /
#       2
#
# Bridge: [1, 3] (removing this disconnects 3 from rest)

// LC 1192 - Critical Connections in a Network
/**
 * time = O(V + E)
 * space = O(V + E)
 */
class Solution {
    private int timer = 0;
    private int[] disc;
    private int[] low;
    private List<List<Integer>> bridges;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        // Build adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (List<Integer> conn : connections) {
            int u = conn.get(0);
            int v = conn.get(1);
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        disc = new int[n];
        low = new int[n];
        bridges = new ArrayList<>();
        Arrays.fill(disc, -1);

        // DFS from vertex 0 (graph is connected in this problem)
        dfs(0, -1, graph);

        return bridges;
    }

    private void dfs(int v, int parent, List<List<Integer>> graph) {
        disc[v] = low[v] = timer++;

        for (int u : graph.get(v)) {
            if (u == parent) continue;  // Skip parent edge

            if (disc[u] == -1) {
                // Unvisited
                dfs(u, v, graph);
                low[v] = Math.min(low[v], low[u]);

                // Check for bridge
                if (low[u] > disc[v]) {
                    bridges.add(Arrays.asList(v, u));
                }
            } else {
                // Back edge
                low[v] = Math.min(low[v], disc[u]);
            }
        }
    }
}

# Tarjan's Algorithm for Articulation Points
def find_articulation_points(n, edges):
    """
    Find all articulation points (cut vertices).

    Args:
        n: number of vertices
        edges: list of [u, v] edges

    Returns:
        Set of articulation points

    Time: O(V + E)
    Space: O(V + E)
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    disc = [-1] * n
    low = [-1] * n
    ap = set()  # Articulation points
    timer = [0]

    def dfs(v, parent):
        children = 0
        disc[v] = low[v] = timer[0]
        timer[0] += 1

        for u in graph[v]:
            if u == parent:
                continue

            if disc[u] == -1:
                # Unvisited child
                children += 1
                dfs(u, v)
                low[v] = min(low[v], low[u])

                # Check if v is articulation point
                # Case 1: Root with 2+ children
                if parent == -1 and children > 1:
                    ap.add(v)

                # Case 2: Non-root with child that can't reach ancestor
                if parent != -1 and low[u] >= disc[v]:
                    ap.add(v)
            else:
                # Back edge
                low[v] = min(low[v], disc[u])

    # Run DFS from each component
    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return list(ap)

# Example:
# n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
#
#    0 --- 1 --- 3 --- 4
#     \   /
#      \ /
#       2
#
# Articulation points: [1, 3]
# (Removing 1 disconnects {0,2} from {3,4})
# (Removing 3 disconnects 4 from rest)

// Articulation Points Algorithm
/**
 * time = O(V + E)
 * space = O(V + E)
 */
class ArticulationPoints {
    private int timer = 0;
    private int[] disc;
    private int[] low;
    private Set<Integer> ap;

    public List<Integer> findArticulationPoints(int n, int[][] edges) {
        // Build adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        disc = new int[n];
        low = new int[n];
        ap = new HashSet<>();
        Arrays.fill(disc, -1);

        // DFS from each component
        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) {
                dfs(i, -1, graph);
            }
        }

        return new ArrayList<>(ap);
    }

    private void dfs(int v, int parent, List<List<Integer>> graph) {
        int children = 0;
        disc[v] = low[v] = timer++;

        for (int u : graph.get(v)) {
            if (u == parent) continue;

            if (disc[u] == -1) {
                children++;
                dfs(u, v, graph);
                low[v] = Math.min(low[v], low[u]);

                // Root with 2+ children
                if (parent == -1 && children > 1) {
                    ap.add(v);
                }

                // Non-root with blocking child
                if (parent != -1 && low[u] >= disc[v]) {
                    ap.add(v);
                }
            } else {
                // Back edge
                low[v] = Math.min(low[v], disc[u]);
            }
        }
    }
}

Graph (Directed):
    0 → 1 → 2
    ↑       ↓
    └───────┘     3 ⇄ 4
                  ↓   ↑
                  5 ──┘

DFS Traversal:

Step 1: Start at 0
  disc[0] = low[0] = 0
  stack = [0]

Step 2: Visit 1 from 0
  disc[1] = low[1] = 1
  stack = [0, 1]

Step 3: Visit 2 from 1
  disc[2] = low[2] = 2
  stack = [0, 1, 2]

Step 4: Back edge 2→0 (0 already on stack)
  low[2] = min(2, disc[0]) = 0
  Backtrack to 1: low[1] = min(1, low[2]) = 0
  Backtrack to 0: low[0] = min(0, low[1]) = 0

Step 5: At 0, low[0] == disc[0] → SCC found!
  Pop stack: [2, 1, 0]
  SCC #1: {0, 1, 2}

Step 6: Start at 3
  disc[3] = low[3] = 3
  stack = [3]

Step 7: Visit 4 from 3
  disc[4] = low[4] = 4
  stack = [3, 4]

Step 8: Visit 5 from 4
  disc[5] = low[5] = 5
  stack = [3, 4, 5]

Step 9: Edge 5→3 (back edge)
  low[5] = min(5, disc[3]) = 3
  Backtrack to 4: low[4] = min(4, low[5]) = 3
  Backtrack to 3: low[3] = min(3, low[4]) = 3

Step 10: At 3, low[3] == disc[3] → SCC found!
  Pop stack: [5, 4, 3]
  SCC #2: {3, 4, 5}

Final SCCs: [{0,1,2}, {3,4,5}]

"critical connections" → Bridges (Tarjan)
"strongly connected" → SCC (Tarjan or Kosaraju)
"cut vertices" → Articulation points (Tarjan)
"remove vertex/edge disconnects graph" → Articulation/Bridge

SCC: Directed graph, maximal mutually reachable sets
Bridges: Undirected graph, critical edges
Articulation Points: Undirected graph, critical vertices

low[v] == disc[v] → Root of SCC (directed)
low[v] > disc[u] → (u,v) is bridge (undirected)
low[v] >= disc[u] → u is articulation point (undirected)

def tarjan_template(v, parent=-1):
    disc[v] = low[v] = timer
    timer += 1

    for u in graph[v]:
        if u == parent:  # Undirected graphs only
            continue

        if disc[u] == -1:
            # Tree edge
            dfs(u, v)
            low[v] = min(low[v], low[u])
            # Check condition here (bridge, AP, etc.)
        else:
            # Back edge
            low[v] = min(low[v], disc[u])  # Or check on_stack for SCC

// java
// LC 753 - Cracking the Safe
// IDEA: de Bruijn graph + Hierholzer Euler circuit.
//       node = (n-1)-digit prefix, edge = one appended digit.
// time = O(k^n), space = O(k^n)
import java.util.*;

public class Solution {
    private Set<String> seen;      // visited EDGES (the n-digit strings)
    private StringBuilder sb;

    public String crackSafe(int n, int k) {
        seen = new HashSet<>();
        sb = new StringBuilder();

        StringBuilder s = new StringBuilder();
        for (int i = 0; i < n - 1; i++) {
            s.append('0');
        }
        String start = s.toString();

        dfs(start, k);
        // post-order emission => append the starting node back at the end
        return sb.toString() + start;
    }

    private void dfs(String node, int k) {
        for (int d = 0; d < k; d++) {
            String edge = node + d;          // the n-digit password = an edge
            if (seen.add(edge)) {            // add() returns false if already used
                dfs(edge.substring(1), k);   // move to next node = drop first digit
                sb.append(d);                // emit AFTER exhausting the subtree
            }
        }
    }
}

# python
# LC 753 - Cracking the Safe
# IDEA: de Bruijn graph + Hierholzer Euler circuit
# time = O(k^n), space = O(k^n)
class Solution(object):
    def crackSafe(self, n, k):
        seen = set()      # visited EDGES (n-digit strings)
        out = []

        def dfs(node):
            for d in map(str, range(k)):
                edge = node + d
                if edge not in seen:
                    seen.add(edge)
                    dfs(edge[1:])     # next node = drop the first digit
                    out.append(d)     # emit AFTER the subtree is exhausted

        start = "0" * (n - 1)
        dfs(start)
        return "".join(out) + start

# crackSafe(2, 2) -> "01100"  (contains 00, 01, 10, 11)
# length is always k^n + n - 1

# python
# time = O(E log E) with sorting, space = O(E)
def euler_path(graph, start):
    """graph: node -> list of next nodes (mutable, consumed as we walk)"""
    stack, route = [start], []
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())   # walk until stuck
        route.append(stack.pop())                  # stuck => this node is final
    return route[::-1]

def is_bipartite_union_find(n, edges):
    """Check bipartite using Union-Find for conflict detection"""

    class UnionFind:
        def __init__(self, n):
            self.parent = list(range(2 * n))  # 2n for opposite groups

        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, x, y):
            px, py = self.find(x), self.find(y)
            if px != py:
                self.parent[px] = py

        def connected(self, x, y):
            return self.find(x) == self.find(y)

    uf = UnionFind(n)

    # For each edge (u,v), union u with opposite of v, and v with opposite of u
    for u, v in edges:
        if uf.connected(u, v):  # Same group conflict
            return False

        # u should be in opposite group of v
        uf.union(u, v + n)  # u with opposite of v
        uf.union(v, u + n)  # v with opposite of u

    return True

def max_bipartite_matching(graph, n, m):
    """Find maximum matching in bipartite graph"""
    match = [-1] * m

    def dfs(u, visited):
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                if match[v] == -1 or dfs(match[v], visited):
                    match[v] = u
                    return True
        return False

    result = 0
    for u in range(n):
        visited = [False] * m
        if dfs(u, visited):
            result += 1

    return result

def validate_bipartite_assignment(assignments, conflicts):
    """
    Validate if assignment is bipartite given conflict pairs
    assignments: list of items to assign
    conflicts: list of (item1, item2) that cannot be in same group
    """
    from collections import defaultdict

    graph = defaultdict(list)
    for u, v in conflicts:
        graph[u].append(v)
        graph[v].append(u)

    colors = {}

    def can_color(item, color):
        if item in colors:
            return colors[item] == color

        colors[item] = color
        for conflict_item in graph[item]:
            if not can_color(conflict_item, 1 - color):
                return False
        return True

    for item in assignments:
        if item not in colors:
            if not can_color(item, 0):
                return False, {}

    # Return partition
    group_a = [item for item, color in colors.items() if color == 0]
    group_b = [item for item, color in colors.items() if color == 1]

    return True, {"Group A": group_a, "Group B": group_b}

# python
# LC 1042 - Flower Planting With No Adjacent
# IDEA: degree <= 3 and 4 colors available => a free color ALWAYS exists.
#       greedy single pass, no bipartite check / no backtracking needed.
# time = O(V + E), space = O(V + E)
from collections import defaultdict

class Solution(object):
    def gardenNoAdj(self, n, paths):
        g = defaultdict(list)
        for a, b in paths:
            g[a].append(b)
            g[b].append(a)

        res = [0] * n                      # res[i-1] = flower type of garden i
        for i in range(1, n + 1):
            used = {res[j - 1] for j in g[i]}   # 0 = "not yet colored"
            res[i - 1] = next(c for c in (1, 2, 3, 4) if c not in used)
        return res

// java
// LC 1042 - Flower Planting With No Adjacent
// time = O(V + E), space = O(V + E)
public int[] gardenNoAdj(int n, int[][] paths) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
        g.add(new ArrayList<>());
    }
    for (int[] p : paths) {
        g.get(p[0]).add(p[1]);
        g.get(p[1]).add(p[0]);
    }

    int[] res = new int[n];
    for (int i = 1; i <= n; i++) {
        boolean[] used = new boolean[5];
        for (int nb : g.get(i)) {
            used[res[nb - 1]] = true;      // res = 0 for uncolored, harmless
        }
        for (int c = 1; c <= 4; c++) {
            if (!used[c]) { res[i - 1] = c; break; }
        }
    }
    return res;
}

from collections import defaultdict, deque

def max_flow(graph, source, sink, n):
    """graph[u][v] = capacity. Returns max flow from source to sink."""
    def bfs(source, sink, parent):
        visited = set([source])
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in range(n):
                if v not in visited and graph[u][v] > 0:
                    visited.add(v)
                    parent[v] = u
                    if v == sink: return True
                    queue.append(v)
        return False

    flow = 0
    while True:
        parent = [-1] * n
        if not bfs(source, sink, parent):
            break
        # Find min capacity along the path
        path_flow = float('inf')
        s = sink
        while s != source:
            u = parent[s]
            path_flow = min(path_flow, graph[u][s])
            s = parent[s]
        # Update capacities
        s = sink
        while s != source:
            u = parent[s]
            graph[u][s] -= path_flow
            graph[s][u] += path_flow
            s = parent[s]
        flow += path_flow
    return flow