Untitled

mail@pastecode.io avatar
unknown
plain_text
25 days ago
1.8 kB
1
Indexable
Never
class Graph {

    private final int V;
    private final int[][] adj;
    private final int[] size;

    public Graph(int V) {
        this.V = V;
        adj = new int[V][V];  // Array to store adjacency list for each vertex
        size = new int[V];    // Array to store the size of each adjacency list
    }

    // Function to check if cycle exists
    private boolean isCyclicUtil(int i, boolean[] visited, boolean[] recStack) {
        if (recStack[i])
            return true;

        if (visited[i])
            return false;

        visited[i] = true;
        recStack[i] = true;

        for (int j = 0; j < size[i]; j++) {
            int c = adj[i][j];
            if (isCyclicUtil(c, visited, recStack))
                return true;
        }

        recStack[i] = false;
        return false;
    }

    private void addEdge(int source, int dest) {
        adj[source][size[source]++] = dest;  // Add destination to the adjacency list of source
    }

    // Returns true if the graph contains a cycle, else false.
    private boolean isCyclic() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];

        for (int i = 0; i < V; i++)
            if (isCyclicUtil(i, visited, recStack))
                return true;

        return false;
    }

    // Driver code
    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        // Function call
        if (graph.isCyclic())
            System.out.println("Graph contains cycle");
        else
            System.out.println("Graph doesn't contain cycle");
    }
}
Leave a Comment