Skip to main content

Command Palette

Search for a command to run...

cycle in graph

Published
1 min readView as Markdown
class Solution {
    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];

        for (int node = 0; node < V; node++) {
            if (!visited[node]) {
                if (dfs(node, -1, visited, adj)) {
                    return true;
                }
            }
        }

        return false;
    }

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

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, node, visited, adj)) {
                    return true;
                }
            } else if (neighbor != parent) {
                return true; // Found a cycle
            }
        }

        return false;
    }
}

More from this blog

Amit singh's blog

235 posts