Skip to main content

Command Palette

Search for a command to run...

cycle in undirected

Published
1 min readView as Markdown




class Solution {
    public boolean isCyclic(int V, int[][] edges) {
        // Create adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for(int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        for(int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
        }

        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];

        // Check for cycles in each component
        for(int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, recStack, adj)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int node, boolean[] visited, boolean[] recStack, List<List<Integer>> adj) {
        visited[node] = true;
        recStack[node] = true;

        for(int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, visited, recStack, adj)) {
                    return true;
                }
            } else if (recStack[neighbor]) {
                // Found a node in recursion stack -> cycle
                return true;
            }
        }

        recStack[node] = false; // Remove from recursion stack
        return false;
    }
}

More from this blog

Amit singh's blog

235 posts