Does the One-Way Network Contain a Circuit

Medium20–25 min

Topics

GraphDFSCycle DetectionDirected Graph

Companies

AmazonGoogleMicrosoftUberFlipkart

You are given a network of one-way roads as an adjacency list of a directed graph. Decide whether it contains a circuit: a route that follows the roads and comes back to the node it started from (a road from a node to itself also counts).

In a directed graph, meeting an already visited node is not enough to prove a circuit; the important thing is whether that node is still on the current search path.

Test Case 1:

Input:graph = [[1,4],[2],[3],[1],[5],[]]

Output:true

Explanation:Matrix rows (row u, column v is 1 when u → v): 0:[0,1,0,0,1,0], 1:[0,0,1,0,0,0], 2:[0,0,0,1,0,0], 3:[0,1,0,0,0,0], 4:[0,0,0,0,0,1], 5:all 0. The roads 1 → 2 → 3 → 1 close a circuit.

Test Case 2:

Input:graph = [[1,2],[2],[]]

Output:false

Explanation:Every road goes “forward”: nothing leads back, so there is no circuit.

Test Case 3:

Input:graph = [[0]]

Output:true

Explanation:A road from the node to itself is already a circuit.

Constraints

◆1 ≤ n ≤ 10 nodes numbered 0 … n-1; graph[u] lists, in increasing order, every node v that has a one-way road u → v (adjacency-list form of a directed graph)
◆There are no repeated roads; a road from a node to itself is allowed and counts as a circuit
◆The graph may be disconnected
◆A circuit is a route that follows the one-way roads and returns to the node it started from; return true if the graph contains one

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Check Whether Each Node Can Return to Itself

Brute

A circuit exists exactly when some node can reach itself by following at least one road. So for every node, run a full search starting from the nodes it points to and see whether the search comes back to that node. n searches, each visiting up to n nodes and E roads: O(n · (n + E)). It is correct but repeats a lot of work.

TimeO(n · (n + E))

SpaceO(n)

Java

Try it out

class Solution {
    private boolean canReturn(int[][] graph, int start) {
        boolean[] seen = new boolean[graph.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int v : graph[start]) {
            if (!seen[v]) {
                seen[v] = true;
                stack.push(v);
            }
        }
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (u == start) return true;
            for (int w : graph[u]) {
                if (!seen[w]) {
                    seen[w] = true;
                    stack.push(w);
                }
            }
        }
        return false;
    }

    public boolean hasCircuit(int[][] graph) {
        for (int start = 0; start < graph.length; start++) {
            if (canReturn(graph, start)) return true;
        }
        return false;
    }
}

Optimal — Depth-First Search With Three States

Optimal

Give each node a state: 0 = not seen yet, 1 = on the current search path (being explored), 2 = completely finished. When exploring node u, look at each road u → v: if v is in state 1, we have found a road back to a node that is still on our current path, which is a circuit. If v is in state 0, explore it. When all roads of u are handled, mark u finished (2). Finished nodes need not be searched again, so every node and road is handled once: O(n + E).

TimeO(n + E)