Does the Road Network Contain a Loop

Medium20–25 min

Topics

GraphDFSBFSCycle DetectionUndirected Graph

Companies

AmazonMicrosoftGoogleAdobeFlipkart

You are given the road network of a region as an adjacency list of an undirected graph. Decide whether there is a loop: a closed route through at least three towns that does not use the same road twice.

A depth-first search that remembers where it came from finds a loop the moment it meets an already visited town by a different road.

Test Case 1:

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

Output:true

Explanation:Adjacency matrix rows for 0-1, 1-2, 2-3, 1-3, 4-5: 0:[0,1,0,0,0,0,0], 1:[1,0,1,1,0,0,0], 2:[0,1,0,1,0,0,0], 3:[0,1,1,0,0,0,0], 4:[0,0,0,0,0,1,0], 5:[0,0,0,0,1,0,0], 6:all 0. The nodes 1, 2, 3 form a loop.

Test Case 2:

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

Output:false

Explanation:A simple chain 0-1-2 has no loop.

Test Case 3:

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

Output:false

Explanation:Two separate single edges: still no loop.

Constraints

◆1 ≤ n ≤ 10 nodes numbered 0 … n-1; graph[u] lists, in increasing order, every neighbour of u (adjacency-list form of an undirected graph)
◆If v is in graph[u] then u is in graph[v]; there are no self-loops and no repeated edges
◆The graph may be disconnected
◆A loop is a path that starts and ends at the same node, uses at least 3 nodes and never repeats an edge; 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 — Remove Each Road and See if Its Ends Stay Connected

Brute

A road lies on a loop exactly when its two ends are still connected after that road is taken away (the other route is the rest of the loop). So for every road (u, v), run a breadth-first search from u that is not allowed to use that road, and see whether it reaches v. If it does for any road, the graph has a loop. E roads, each costing one search: O(E · (n + E)).

TimeO(E · (n + E))

SpaceO(n)

Java

Try it out

class Solution {
    private boolean connectedWithout(int[][] graph, int a, int b) {
        boolean[] seen = new boolean[graph.length];
        Deque<Integer> queue = new ArrayDeque<>();
        seen[a] = true;
        queue.add(a);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (u == b) return true;
            for (int w : graph[u]) {
                if (u == a && w == b) continue;
                if (!seen[w]) {
                    seen[w] = true;
                    queue.add(w);
                }
            }
        }
        return false;
    }

    public boolean hasLoop(int[][] graph) {
        for (int u = 0; u < graph.length; u++) {
            for (int v : graph[u]) {
                if (u < v && connectedWithout(graph, u, v)) return true;
            }
        }
        return false;
    }
}

Optimal — Depth-First Search Remembering the Parent

Optimal

Explore with a depth-first search and remember the node you came from (the parent). Every neighbour is either the parent (just the road you arrived by, ignore it), an unvisited node (go deeper), or a node that was ALREADY visited and is not the parent. The last case means there are two different ways to reach it, which is exactly a loop. Do this from every unvisited node to cover all separate groups. Each road is seen twice: O(n + E).

TimeO(n + E)