Advanced Graphs: Euler Paths, Bridges & SCCs

1/** Directed graph on 0..n−1. Returns the vertex an Euler path must start from, or -1 if none can exist. */2static int startVertex(int n, int[][] edges) {3    int[] out = new int[n], in = new int[n];4    for (int[] e : edges) {5        out[e[0]]++;6        in[e[1]]++;7    }8    int start = -1, starts = 0, ends = 0;9    for (int v = 0; v < n; v++) {10        int diff = out[v] - in[v];11        if (diff == 1) {12            starts++;13            start = v; // one more edge out than in: the path must begin here14        } else if (diff == -1) {15            ends++; // one more edge in than out: the path ends here16        } else if (diff != 0) {17            return -1; // off by 2 or more: impossible18        }19    }20    if (starts == 1 && ends == 1) return start; // an Euler PATH21    if (starts > 0 || ends > 0) return -1;22    for (int v = 0; v < n; v++) if (out[v] > 0) return v; // an Euler CIRCUIT: start anywhere with an edge23    return 0; // no edges at all24}

1/** An Euler path as a list of vertices, or an empty list if the edges can't be walked in one go. */2static List<Integer> eulerPath(int n, int[][] edges) {3    int start = startVertex(n, edges);4    if (start == -1) return List.of();5    List<List<Integer>> adj = new ArrayList<>();6    for (int v = 0; v < n; v++) adj.add(new ArrayList<>());7    for (int[] e : edges) adj.get(e[0]).add(e[1]);8    int[] used = new int[n]; // used[u] = how many of u's edges are already walked9    Deque<Integer> stack = new ArrayDeque<>(List.of(start));10    List<Integer> path = new ArrayList<>();11    while (!stack.isEmpty()) {12        int u = stack.peek();13        if (used[u] < adj.get(u).size()) {14            stack.push(adj.get(u).get(used[u]++)); // walk an unused edge15        } else {16            path.add(stack.pop()); // stuck: u is final, counted from the end17        }18    }19    Collections.reverse(path);20    return path.size() == edges.length + 1 ? path : List.of(); // fewer → some edges were unreachable21}

1class BridgeFinder {2    private List<List<Integer>> adj;3    private int[] tin, low; // discovery time · lowest time the subtree can reach with one back edge4    private int timer;5    private final List<int[]> bridges = new ArrayList<>();6 7    /** Undirected graph on 0..n−1, no parallel edges. Works on disconnected graphs too. */8    List<int[]> find(int n, int[][] edges) {9        adj = new ArrayList<>();10        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());11        for (int[] e : edges) {12            adj.get(e[0]).add(e[1]);13            adj.get(e[1]).add(e[0]);14        }15        tin = new int[n];16        low = new int[n];17        Arrays.fill(tin, -1);18        for (int s = 0; s < n; s++) if (tin[s] == -1) dfs(s, -1);19        return bridges;20    }21 22    private void dfs(int u, int parent) {23        tin[u] = low[u] = timer++;24        for (int v : adj.get(u)) {25            if (v == parent) continue; // the edge we came in on doesn't count26            if (tin[v] != -1) {27                low[u] = Math.min(low[u], tin[v]); // back edge: a second way up28            } else {29                dfs(v, u);30                low[u] = Math.min(low[u], low[v]);31                if (low[v] > tin[u]) bridges.add(new int[] {u, v}); // v's side can't reach u or above32            }33        }34    }35}

1class CutVertexFinder {2    private List<List<Integer>> adj;3    private int[] tin, low;4    private boolean[] cut;5    private int timer;6 7    /** Vertices whose removal splits their connected component, in increasing order. */8    List<Integer> find(int n, int[][] edges) {9        adj = new ArrayList<>();10        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());11        for (int[] e : edges) {12            adj.get(e[0]).add(e[1]);13            adj.get(e[1]).add(e[0]);14        }15        tin = new int[n];16        low = new int[n];17        cut = new boolean[n];18        Arrays.fill(tin, -1);19        for (int s = 0; s < n; s++) if (tin[s] == -1) dfs(s, -1);20        List<Integer> out = new ArrayList<>();21        for (int v = 0; v < n; v++) if (cut[v]) out.add(v);22        return out;23    }24 25    private void dfs(int u, int parent) {26        tin[u] = low[u] = timer++;27        int children = 0;28        for (int v : adj.get(u)) {29            if (v == parent) continue;30            if (tin[v] != -1) {31                low[u] = Math.min(low[u], tin[v]);32            } else {33                dfs(v, u);34                children++;35                low[u] = Math.min(low[u], low[v]);36                if (parent != -1 && low[v] >= tin[u]) cut[u] = true; // v's side can't get above u37            }38        }39        if (parent == -1 && children > 1) cut[u] = true; // a root is a cut vertex iff it has 2+ DFS children40    }41}

1class Solution {2    private List<List<Integer>> adj;3    private int[] tin, low; // discovery time · lowest time the subtree can reach with one back edge4    private int timer;5    private List<List<Integer>> bridges;6 7    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {8        adj = new ArrayList<>();9        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10        for (List<Integer> c : connections) {11            adj.get(c.get(0)).add(c.get(1));12            adj.get(c.get(1)).add(c.get(0));13        }14        tin = new int[n];15        low = new int[n];16        Arrays.fill(tin, -1); // -1 = not visited yet17        timer = 0;18        bridges = new ArrayList<>();19        dfs(0, -1); // the network is connected, so one DFS reaches every server20        return bridges;21    }22 23    private void dfs(int u, int parent) {24        tin[u] = low[u] = timer++;25        for (int v : adj.get(u)) {26            if (v == parent) continue; // the edge we came in on doesn't count27            if (tin[v] != -1) {28                low[u] = Math.min(low[u], tin[v]); // back edge: a second way up29            } else {30                dfs(v, u); // tree edge: explore v's side first31                low[u] = Math.min(low[u], low[v]);32                if (low[v] > tin[u]) bridges.add(List.of(u, v)); // v's side can't reach u or above33            }34        }35    }36}

1class Solution {2    /** The same low-link DFS with an explicit stack: no StackOverflowError on a 10⁵-server chain. */3    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());6        for (List<Integer> c : connections) {7            adj.get(c.get(0)).add(c.get(1));8            adj.get(c.get(1)).add(c.get(0));9        }10        int[] tin = new int[n], low = new int[n], parent = new int[n];11        int[] next = new int[n]; // next[u] = index of u's next neighbour to look at12        Arrays.fill(tin, -1);13        List<List<Integer>> bridges = new ArrayList<>();14        Deque<Integer> stack = new ArrayDeque<>(List.of(0));15        int timer = 0;16        tin[0] = low[0] = timer++;17        parent[0] = -1;18        while (!stack.isEmpty()) {19            int u = stack.peek();20            if (next[u] < adj.get(u).size()) {21                int v = adj.get(u).get(next[u]++);22                if (v == parent[u]) continue;23                if (tin[v] != -1) {24                    low[u] = Math.min(low[u], tin[v]); // back edge25                } else {26                    tin[v] = low[v] = timer++; // tree edge: "call" v27                    parent[v] = u;28                    stack.push(v);29                }30            } else {31                stack.pop(); // u is finished: "return" to its parent32                int p = parent[u];33                if (p == -1) continue;34                low[p] = Math.min(low[p], low[u]);35                if (low[u] > tin[p]) bridges.add(List.of(p, u));36            }37        }38        return bridges;39    }40}

1class TarjanScc {2    private List<List<Integer>> adj;3    private int[] tin, low, comp;4    private boolean[] onStack;5    private final Deque<Integer> stack = new ArrayDeque<>();6    private int timer, count;7 8    /** comp[v] = id of v's component. Ids come out in REVERSE topological order (sinks first). */9    int[] components(int n, int[][] edges) {10        adj = new ArrayList<>();11        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());12        for (int[] e : edges) adj.get(e[0]).add(e[1]);13        tin = new int[n];14        low = new int[n];15        comp = new int[n];16        onStack = new boolean[n];17        Arrays.fill(tin, -1);18        for (int v = 0; v < n; v++) if (tin[v] == -1) dfs(v);19        return comp;20    }21 22    private void dfs(int u) {23        tin[u] = low[u] = timer++;24        stack.push(u);25        onStack[u] = true;26        for (int v : adj.get(u)) {27            if (tin[v] == -1) {28                dfs(v);29                low[u] = Math.min(low[u], low[v]);30            } else if (onStack[v]) {31                low[u] = Math.min(low[u], tin[v]); // v is in the component still being built32            }33        }34        if (low[u] == tin[u]) { // nothing below u reaches above it: u roots a component35            int v;36            do {37                v = stack.pop();38                onStack[v] = false;39                comp[v] = count;40            } while (v != u);41            count++;42        }43    }44}

1class Kosaraju {2    /** comp[v] = id of v's strongly connected component. Ids follow a topological order of the components. */3    int[] components(int n, int[][] edges) {4        List<List<Integer>> adj = new ArrayList<>(), reversed = new ArrayList<>();5        for (int v = 0; v < n; v++) {6            adj.add(new ArrayList<>());7            reversed.add(new ArrayList<>());8        }9        for (int[] e : edges) {10            adj.get(e[0]).add(e[1]);11            reversed.get(e[1]).add(e[0]);12        }13        boolean[] seen = new boolean[n];14        Deque<Integer> finished = new ArrayDeque<>();15        for (int v = 0; v < n; v++) {16            if (!seen[v]) finishOrder(v, adj, seen, finished); // pass 117        }18        int[] comp = new int[n];19        Arrays.fill(comp, -1);20        int count = 0;21        while (!finished.isEmpty()) {22            int v = finished.pop(); // latest finisher first23            if (comp[v] == -1) collect(v, count++, reversed, comp); // pass 2, on reversed edges24        }25        return comp;26    }27 28    private void finishOrder(int u, List<List<Integer>> adj, boolean[] seen, Deque<Integer> finished) {29        seen[u] = true;30        for (int v : adj.get(u)) {31            if (!seen[v]) finishOrder(v, adj, seen, finished);32        }33        finished.push(u); // u finishes after everything it reaches34    }35 36    private void collect(int u, int id, List<List<Integer>> reversed, int[] comp) {37        comp[u] = id;38        for (int v : reversed.get(u)) {39            if (comp[v] == -1) collect(v, id, reversed, comp);40        }41    }42}

1class Solution {2    private Map<String, String> parent;3    private Map<String, Double> weight; // weight.get(x) = x / parent(x)4 5    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {6        parent = new HashMap<>();7        weight = new HashMap<>();8        for (int i = 0; i < equations.size(); i++) union(equations.get(i).get(0), equations.get(i).get(1), values[i]);9        double[] answers = new double[queries.size()];10        for (int q = 0; q < queries.size(); q++) {11            String c = queries.get(q).get(0), d = queries.get(q).get(1);12            if (!parent.containsKey(c) || !parent.containsKey(d) || !find(c).equals(find(d))) answers[q] = -1.0;13            else answers[q] = weight.get(c) / weight.get(d); // (c / root) / (d / root) = c / d14        }15        return answers;16    }17 18    /** Returns x's root and flattens the path; afterwards weight(x) = x / root. */19    private String find(String x) {20        String p = parent.get(x);21        if (p.equals(x)) return x;22        String root = find(p);23        weight.put(x, weight.get(x) * weight.get(p)); // (x / p) * (p / root)24        parent.put(x, root);25        return root;26    }27 28    /** Records a / b = value by hanging a's root under b's root. */29    private void union(String a, String b, double value) {30        for (String s : List.of(a, b)) {31            parent.putIfAbsent(s, s);32            weight.putIfAbsent(s, 1.0);33        }34        String ra = find(a), rb = find(b);35        if (ra.equals(rb)) return;36        parent.put(ra, rb);37        weight.put(ra, value * weight.get(b) / weight.get(a)); // ra / rb = (a / b) * (b / rb) / (a / ra)38    }39}

1class Solution {2    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {3        Map<String, Map<String, Double>> graph = new HashMap<>(); // graph.get(a).get(b) = a / b4        for (int i = 0; i < equations.size(); i++) {5            String a = equations.get(i).get(0), b = equations.get(i).get(1);6            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);7            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]);8        }9        double[] answers = new double[queries.size()];10        for (int q = 0; q < queries.size(); q++) {11            String c = queries.get(q).get(0), d = queries.get(q).get(1);12            if (!graph.containsKey(c) || !graph.containsKey(d)) answers[q] = -1.0; // never seen13            else answers[q] = walk(c, d, 1.0, graph, new HashSet<>());14        }15        return answers;16    }17 18    /** product = start / cur so far. Returns start / target, or -1 if target can't be reached. */19    private double walk(String cur, String target, double product, Map<String, Map<String, Double>> graph, Set<String> seen) {20        if (cur.equals(target)) return product;21        seen.add(cur);22        for (Map.Entry<String, Double> edge : graph.get(cur).entrySet()) {23            if (seen.contains(edge.getKey())) continue;24            double result = walk(edge.getKey(), target, product * edge.getValue(), graph, seen);25            if (result != -1.0) return result;26        }27        return -1.0; // dead end: back up28    }29}