import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

/** Runnable companion to the BFS and DFS article. Node IDs are 0 through n - 1. */
public class BfsDfsExamples {
    public record BfsResult(List<Integer> order, int[] distance, int[] parent) {}

    public static List<List<Integer>> graph(int n, int[][] edges, boolean directed) {
        if (n < 0) throw new IllegalArgumentException("Node count cannot be negative");
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            if (edge.length != 2 || edge[0] < 0 || edge[1] < 0 || edge[0] >= n || edge[1] >= n) {
                throw new IllegalArgumentException("Every edge needs two valid node IDs");
            }
            graph.get(edge[0]).add(edge[1]);
            if (!directed) graph.get(edge[1]).add(edge[0]);
        }
        return graph;
    }

    private static void checkStart(List<List<Integer>> graph, int start) {
        if (start < 0 || start >= graph.size()) throw new IllegalArgumentException("Invalid start node");
    }

    public static BfsResult bfs(List<List<Integer>> graph, int start) {
        checkStart(graph, start);
        int[] distance = new int[graph.size()];
        int[] parent = new int[graph.size()];
        Arrays.fill(distance, -1);
        Arrays.fill(parent, -1);
        List<Integer> order = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        distance[start] = 0;
        queue.offer(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int next : graph.get(node)) {
                if (distance[next] == -1) {
                    distance[next] = distance[node] + 1;
                    parent[next] = node;
                    queue.offer(next);
                }
            }
        }
        return new BfsResult(order, distance, parent);
    }

    public static List<Integer> pathTo(BfsResult result, int target) {
        if (target < 0 || target >= result.distance().length) throw new IllegalArgumentException("Invalid target");
        if (result.distance()[target] == -1) return List.of();
        List<Integer> path = new ArrayList<>();
        for (int node = target; node != -1; node = result.parent()[node]) path.add(node);
        Collections.reverse(path);
        return path;
    }

    public static List<Integer> dfsRecursive(List<List<Integer>> graph, int start) {
        checkStart(graph, start);
        boolean[] visited = new boolean[graph.size()];
        List<Integer> order = new ArrayList<>();
        visit(graph, start, visited, order);
        return order;
    }

    private static void visit(List<List<Integer>> graph, int node,
                              boolean[] visited, List<Integer> order) {
        visited[node] = true;
        order.add(node);
        for (int next : graph.get(node)) {
            if (!visited[next]) visit(graph, next, visited, order);
        }
    }

    private static class Frame {
        final int node;
        int next;
        Frame(int node) { this.node = node; }
    }

    public static List<Integer> dfsStack(List<List<Integer>> graph, int start) {
        checkStart(graph, start);
        boolean[] visited = new boolean[graph.size()];
        List<Integer> order = new ArrayList<>();
        Deque<Frame> stack = new ArrayDeque<>();
        visited[start] = true;
        order.add(start);
        stack.push(new Frame(start));
        while (!stack.isEmpty()) {
            Frame frame = stack.peek();
            if (frame.next == graph.get(frame.node).size()) {
                stack.pop();
                continue;
            }
            int next = graph.get(frame.node).get(frame.next++);
            if (!visited[next]) {
                visited[next] = true;
                order.add(next);
                stack.push(new Frame(next));
            }
        }
        return order;
    }

    // A simpler pending-node stack. Duplicates can wait in the stack; skip them on pop.
    public static List<Integer> dfsPendingStack(List<List<Integer>> graph, int start) {
        checkStart(graph, start);
        boolean[] visited = new boolean[graph.size()];
        List<Integer> order = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (visited[node]) continue;
            visited[node] = true;
            order.add(node);
            List<Integer> neighbors = graph.get(node);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int next = neighbors.get(i);
                if (!visited[next]) stack.push(next);
            }
        }
        return order;
    }

    // Only for an undirected graph. Directed components need a different definition.
    public static int countComponents(List<List<Integer>> graph) {
        boolean[] visited = new boolean[graph.size()];
        int components = 0;
        for (int node = 0; node < graph.size(); node++) {
            if (!visited[node]) {
                components++;
                visit(graph, node, visited, new ArrayList<>());
            }
        }
        return components;
    }

    public static int[] multiSourceDistances(List<List<Integer>> graph, int[] sources) {
        int[] distance = new int[graph.size()];
        Arrays.fill(distance, -1);
        Queue<Integer> queue = new ArrayDeque<>();
        for (int source : sources) {
            checkStart(graph, source);
            if (distance[source] == -1) {
                distance[source] = 0;
                queue.offer(source);
            }
        }
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : graph.get(node)) {
                if (distance[next] == -1) {
                    distance[next] = distance[node] + 1;
                    queue.offer(next);
                }
            }
        }
        return distance;
    }

    // Does not mutate the grid. Valid cells are '0' and '1'; rows must be rectangular.
    public static int countIslands(char[][] grid) {
        if (grid.length == 0) return 0;
        int rows = grid.length, columns = grid[0].length;
        for (char[] row : grid) if (row.length != columns) throw new IllegalArgumentException("Grid must be rectangular");
        boolean[][] seen = new boolean[rows][columns];
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int islands = 0;
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (grid[row][column] != '1' || seen[row][column]) continue;
                islands++;
                Queue<int[]> queue = new ArrayDeque<>();
                seen[row][column] = true;
                queue.offer(new int[]{row, column});
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] direction : directions) {
                        int nextRow = cell[0] + direction[0];
                        int nextColumn = cell[1] + direction[1];
                        if (nextRow >= 0 && nextRow < rows && nextColumn >= 0 && nextColumn < columns
                                && grid[nextRow][nextColumn] == '1' && !seen[nextRow][nextColumn]) {
                            seen[nextRow][nextColumn] = true;
                            queue.offer(new int[]{nextRow, nextColumn});
                        }
                    }
                }
            }
        }
        return islands;
    }

    public static boolean isBipartite(List<List<Integer>> graph) {
        int[] color = new int[graph.size()];
        Arrays.fill(color, -1);
        for (int start = 0; start < graph.size(); start++) {
            if (color[start] != -1) continue;
            Queue<Integer> queue = new ArrayDeque<>();
            color[start] = 0;
            queue.offer(start);
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int next : graph.get(node)) {
                    if (color[next] == -1) {
                        color[next] = 1 - color[node];
                        queue.offer(next);
                    } else if (color[next] == color[node]) return false;
                }
            }
        }
        return true;
    }

    public static boolean hasDirectedCycle(List<List<Integer>> graph) {
        int[] state = new int[graph.size()];
        for (int node = 0; node < graph.size(); node++) {
            if (state[node] == 0 && cycleFrom(graph, node, state)) return true;
        }
        return false;
    }

    private static boolean cycleFrom(List<List<Integer>> graph, int node, int[] state) {
        state[node] = 1;
        for (int next : graph.get(node)) {
            if (state[next] == 1) return true;
            if (state[next] == 0 && cycleFrom(graph, next, state)) return true;
        }
        state[node] = 2;
        return false;
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = graph(7, new int[][]{
                {0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}
        }, false);
        BfsResult result = bfs(graph, 0);
        System.out.println("BFS: " + result.order());
        System.out.println("Distances: " + Arrays.toString(result.distance()));
        System.out.println("Path to G: " + pathTo(result, 6));
        System.out.println("Recursive DFS: " + dfsRecursive(graph, 0));
        System.out.println("Frame-stack DFS: " + dfsStack(graph, 0));
        System.out.println("Pending-stack DFS: " + dfsPendingStack(graph, 0));
    }
}
