// Path: src/main/java/io/github/marioluan/datastructures/graph/Digraph.java
// public class Digraph implements Graph {
//     private final int V;
//     private int E;
//     private Bag<Integer>[] adj;
// 
//     /**
//      * Creates an empty {@link Digraph}.<br>
//      * time complexity: O(V)
//      *
//      * @param V number of vertices
//      */
//     public Digraph(int V) {
//         this.V = V;
//         adj = (Bag<Integer>[]) new Bag[V];
//         IntStream.range(0, V).forEach(v -> adj[v] = new Bag<>());
//         E = 0;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public void addEdge(int v, int w) {
//         adj[v].add(w);
//         E++;
//     }
// 
//     // time complexity: outdegree(v)
//     @Override
//     public Iterable<Integer> adj(int v) {
//         return adj[v];
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int V() {
//         return V;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int E() {
//         return E;
//     }
// 
//     @Override
//     public Graph reverse() {
//         Digraph reversed = new Digraph(V);
// 
//         for (int i = 0; i < V; i++)
//             for (int s : adj(i))
//                 reversed.addEdge(s, i);
// 
//         return reversed;
//     }
// 
//     // TODO: implement me!
//     @Override
//     public String toString() {
//         return null;
//     }
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/graph/sort/TopologicalSort.java
// public class TopologicalSort {
//     private Graph graph;
//     private LinkedList<Integer> reversePost;
//     private boolean[] marked;
// 
//     /**
//      * Performs a DFS and sort graph's vertices in topological order.
//      *
//      * @param graph the graph to be sorted
//      */
//     public TopologicalSort(Graph graph) {
//         // TODO: validate if graph is acyclic (it cannot have cycles)
//         this.graph = graph;
//         reversePost = new LinkedList<>();
//         marked = new boolean[graph.V()];
// 
//         search();
//     }
// 
//     /**
//      * Performs a DFS from each vertex in the graph.
//      */
//     private void search() {
//         for (int s = 0; s < graph.V(); s++)
//             // do not traverse the same vertex twice
//             if (!marked[s])
//                 search(s);
//     }
// 
//     /**
//      * Performs a DFS from vertex s to its adjacent vertices.
//      *
//      * @param s source vertex
//      */
//     private void search(int s) {
//         // tell the world, we already visited it
//         marked[s] = true;
// 
//         // go deep into its adjacent vertices
//         for (int v : graph.adj(s))
//             // repeat the same process for its adjacent vertex
//             // only if we have not done it before
//             if (!marked[v])
//                 search(v);
// 
//         // when we reached the last adjacent vertex of s
//         reversePost.push(s);
//     }
// 
//     /**
//      * Returns the vertices in reverse postorder.
//      *
//      * @return the vertices in reverse postorder
//      */
//     public Iterable<Integer> reversePost() {
//         return reversePost;
//     }
// }


import io.github.marioluan.datastructures.graph.Digraph;
import io.github.marioluan.datastructures.graph.sort.TopologicalSort;
    }

    /**
     * Returns the number of components.
     *
     * @return the number of components
     */
    public int getCount() {
        return count;
    }

    /**
     * Returns the component's id of the vertex v.
     *
     * @param v a given vertex
     * @return the component's id of the vertex v.
     */
    public int id(int v) {
        return id[v];
    }

    /**
     * Returns whether vertices s and v are strongly-connected.
     *
     * @param s source vertex
     * @param v destination vertex
     * @return whether vertices s and v are strongly-connected
     */
    // Time complexity: O(1)
    public boolean stronglyConnected(int s, int v) {
// Path: src/main/java/io/github/marioluan/datastructures/graph/Digraph.java
// public class Digraph implements Graph {
//     private final int V;
//     private int E;
//     private Bag<Integer>[] adj;
// 
//     /**
//      * Creates an empty {@link Digraph}.<br>
//      * time complexity: O(V)
//      *
//      * @param V number of vertices
//      */
//     public Digraph(int V) {
//         this.V = V;
//         adj = (Bag<Integer>[]) new Bag[V];
//         IntStream.range(0, V).forEach(v -> adj[v] = new Bag<>());
//         E = 0;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public void addEdge(int v, int w) {
//         adj[v].add(w);
//         E++;
//     }
// 
//     // time complexity: outdegree(v)
//     @Override
//     public Iterable<Integer> adj(int v) {
//         return adj[v];
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int V() {
//         return V;
//     }
// 
//     // time complexity: O(1)
//     @Override
//     public int E() {
//         return E;
//     }
// 
//     @Override
//     public Graph reverse() {
//         Digraph reversed = new Digraph(V);
// 
//         for (int i = 0; i < V; i++)
//             for (int s : adj(i))
//                 reversed.addEdge(s, i);
// 
//         return reversed;
//     }
// 
//     // TODO: implement me!
//     @Override
//     public String toString() {
//         return null;
//     }
// }
// 
// Path: src/main/java/io/github/marioluan/datastructures/graph/sort/TopologicalSort.java
// public class TopologicalSort {
//     private Graph graph;
//     private LinkedList<Integer> reversePost;
//     private boolean[] marked;
// 
//     /**
//      * Performs a DFS and sort graph's vertices in topological order.
//      *
//      * @param graph the graph to be sorted
//      */
//     public TopologicalSort(Graph graph) {
//         // TODO: validate if graph is acyclic (it cannot have cycles)
//         this.graph = graph;
//         reversePost = new LinkedList<>();
//         marked = new boolean[graph.V()];
// 
//         search();
//     }
// 
//     /**
//      * Performs a DFS from each vertex in the graph.
//      */
//     private void search() {
//         for (int s = 0; s < graph.V(); s++)
//             // do not traverse the same vertex twice
//             if (!marked[s])
//                 search(s);
//     }
// 
//     /**
//      * Performs a DFS from vertex s to its adjacent vertices.
//      *
//      * @param s source vertex
//      */
//     private void search(int s) {
//         // tell the world, we already visited it
//         marked[s] = true;
// 
//         // go deep into its adjacent vertices
//         for (int v : graph.adj(s))
//             // repeat the same process for its adjacent vertex
//             // only if we have not done it before
//             if (!marked[v])
//                 search(v);
// 
//         // when we reached the last adjacent vertex of s
//         reversePost.push(s);
//     }
// 
//     /**
//      * Returns the vertices in reverse postorder.
//      *
//      * @return the vertices in reverse postorder
//      */
//     public Iterable<Integer> reversePost() {
//         return reversePost;
//     }
// }


// Path: src/main/java/io/github/marioluan/datastructures/graph/search/StronglyConnectedComponents.java
import io.github.marioluan.datastructures.graph.Digraph;
import io.github.marioluan.datastructures.graph.sort.TopologicalSort;

    }

    /**
     * Returns the number of components.
     *
     * @return the number of components
     */
    public int getCount() {
        return count;
    }

    /**
     * Returns the component's id of the vertex v.
     *
     * @param v a given vertex
     * @return the component's id of the vertex v.
     */
    public int id(int v) {
        return id[v];
    }

    /**
     * Returns whether vertices s and v are strongly-connected.
     *
     * @param s source vertex
     * @param v destination vertex
     * @return whether vertices s and v are strongly-connected
     */
    // Time complexity: O(1)
    public boolean stronglyConnected(int s, int v) {
        return id[s] == id[v];